← 返回题目列表

AtCoder · awc0071_a

A. 括号的深度

中文机器翻译题面 查看原题

分数: 233 分

问题陈述

Takahashi 正在创建一个程序来分析数学表达式中包含的括号的结构。

在数学表达式中,括号用于表示计算的优先级。括号可以嵌套,并且通过在括号内包含更多括号,可以指定复杂的计算顺序。高桥决定首先只提取括号并检查它们的嵌套深度。

给你一个字符串 S 仅包含 ( 和 )。让 N 的长度 S,并将字符串从开头开始的每个字符编号为 1圣, 2nd, \ldots, N第一个字符。的 深度 在 i- 第一个字符定义为 ( 减去 ) 之前的所有字符 i- 第一个字符(即,从 1st 到 (i-1)- 第一个字符)。当 i = 1,前面没有字符,所以深度为 0.

例如,每个字符的深度 ((())) 是,从左到右, 0, 1, 2, 3, 2, 1。对于 4第一个字符 ),全部 3 之前的字符是 (,所以深度是 3 - 0 = 3。该字符串的最大深度是 3。另外,每个角色的深度 (()()) 是,从左到右, 0, 1, 2, 1, 2, 1,最大深度为 2.

给定字符串 S,找到所有字符深度中的最大值 S.

约束

  • 2 \leq N \leq 10^6 (N 是字符串的长度 S)
  • S 仅包含 ( 和 )
  • S 是正确匹配的括号序列。即满足以下两个条件:
  • 从开始的任意位置, ( 至少是 )
  • 在整个字符串中, ( 和 ) 相等

输入

S
  • 第一行包含括号字符串 S。输入仅包含这一行。

输出

打印所有字符深度中的最大值 S 一行。


示例输入 1

((()))

示例输出 1

3

示例输入 2

(()(())(()))

示例输出 2

3

示例输入 3

((((()))))((()))(())()(((((())))))

示例输出 3

6