【Hard】给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
假设字符串为S
动态规划
一开始我连动态规划的“通项式”都想的稀里糊涂的…
动态规划的要点在于写出第i项的通项公式。在这个题中，dp[i]的值表示以第i个字符为结束字符的最长有效子串的长度。那么S[i]必然要求得是 ) ，以 ( 结尾的 dp 值应该都是0。所以只需要计算 ) 的dp值，取最大的即可。
根据经验，想象一下，一般来说的有效括号是 e() 或者 (e)。其中e是已知的有效子串，即dp[i-1]。
如果S[i] ==
)&& S[i-1] ==(:
dp[i] = dp[i-2] + 2如果S[i] ==
)&& S[i-1] ==)&& S[i-dp[i-1]-1] ==(
dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
重点在于：还要加一个dp[i-dp[i-1]-2]，你细品…
算法复杂度没什么好说
时间复杂度：O(n)
空间复杂度：O(n)
当我以为动态规划法应该是效率最高的，结果看了一下discuss，还是“山外有山，人外有人”啊。
栈
栈确实是括号的匹配的常用算法。不过之前只见过用于判断字符串是否合法。一般可以通过A用法…衍生一下…变为B用法。
遍历字符串
- 如果是
(，那么把当前的索引入栈。 - 如果是
)，那么把栈顶的出栈，与当前的索引值求差值，这个差值，便可用于更新最大值。如果栈底空了，就放弃当前这个字符。
不过这里再细品一下，似乎栈的使用与动态规划如出一辙，只不过动态规划中的dp[<i]存储的是每一个i下的结果值，而本题目只需要一个最大值。栈存储的是索引，所以也可以求出最大值。
时间复杂度：O(n)
空间复杂度：O(n)
计数器法
我一直在思考这个方法应该怎么去理解它…
括号匹配的子串其实只需要满足以下 两 个条件就可以：
(和)的数量一致- 第一个必须得是
(, 最后一个必须得是)
第一个条件，可以通过计数来搞定。第二个可以通过正反两次遍历来搞定。
正向遍历的时候，如果)的数量 >(的数量了（其实也就是出现了 e) 的情况，e是有效子串），那么就重置数量计算。
反向遍历的时候，如果(的数量 >)的数量了（其实也就是出现了 (e 的情况，e是有效子串），那么就重置数量计算。
时间复杂度：O(n)
空间复杂度：O(1)