概要

与えられた正しい括弧列に対して、括弧の入れ子の最大の深さを求めます。

考察

この問題では、括弧の深さを管理しながら文字列を左から右に見ていき、最大の深さを記録すれば良いです。

• ( が現れると深さが1増える
• ) が現れると深さが1減る

これはスタックのような動作ですが、実際には深さを数値で管理するだけで十分です。各 ( に対して対応する ) が必ず存在することが保証されているため、深さが負になることはありません。

素朴な方法として、再帰的に括弧の深さを調べるなどが考えられますが、文字列の長さが最大 \(10^6\) あるため、再帰はスタックオーバーフローのリスクがあります。また、毎回部分文字列を切り出すような処理を行うと、時間計算量が大きくなります。

この問題では、1パスで深さを更新していく線形時間のアルゴリズムが最適です。

例えば、文字列 (()(())) を見てみましょう：

文字	深さ	最大深さ
(	1	1
(	2	2
)	1	2
(	2	2
(	3	3
)	2	3
)	1	3
)	0	3

このように、各文字に対して深さを更新していけば、最終的に最大の深さが求められます。

アルゴリズム

1. 変数 depth を現在の深さ、max_depth をこれまでの最大深さとして保持します。
2. 文字列を左から右に走査します：
   • ( なら depth を1増やし、max_depth を更新します（必要なら）
   • ) なら depth を1減らします
3. 走査終了後、max_depth を出力します

計算量

• 時間計算量: \(O(|S|)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 各文字に対して一度だけ処理を行うため、非常に効率的です

• 入力文字列の前後の空白を取り除くために .strip() を使うと安全です

• max_depth は ( のときだけチェックすれば十分です（) では減少するだけなので最大値は更新されない）

  ソースコード

s = input().strip()

depth = 0
max_depth = 0

for char in s:
    if char == '(':
        depth += 1
        max_depth = max(max_depth, depth)
    elif char == ')':
        depth -= 1

print(max_depth)

---

この解説は qwen3-coder-480b によって生成されました。