分数: 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