32. 最长有效括号

题目：https://leetcode-cn.com/problems/longest-valid-parentheses/submissions/

代码：

class Solution {
    public int longestValidParentheses(String s) {
        if (s==null || s.length()==0){
            return 0;
        }
        int max = 0;
        int current = 0;
        int sum = 0;
        //正向查找
        for (int i = 0; i < s.length(); i++) {
            sum += s.charAt(i)=='('?1:-1;
            current++;
            if (sum == 0) {
                max = Math.max(max,current);
            }else if (sum<0){
                current = 0;
                sum = 0;
            }
        }
        current = 0;
        sum = 0;
        //反向查找
        for (int i = s.length()-1; i >= 0; i--) {
            sum += s.charAt(i)==')'?1:-1;
            current++;
            if (sum == 0) {
                max = Math.max(max,current);
            }else if (sum<0){
                current = 0;
                sum = 0;
            }
        }
        return max;
    }
}

思路：因为括号只有()这两种符号，那么暂定(=1，)=-1,那么有效符号字串s转换成数字加减之后。和必定是0。

所以遍历字符串，用current来记录每次遍历字串的长度，在sum=0的时候，认为是一个有效的字串，则将其记录起来（因为只需要最长字串，所以只有当max < current的时候才记录）。在sum < 0的时候，这个时候无论字串后面再来什么符号，这个字串肯定是一个无效的字串，所以我们直接将current和sum清零，并从下一位重新开始寻找新的字串。

以上是正向查找的原因，但是为什么正向查找之后还需要反向查找一次并取两次的最大值呢？目的是解决“(()”这种情况，这种情况下如果正向查找的话因为sum还没有为0过，所以得出结果会为0。因为括号的特殊性，所以将其反向查找一遍。反向查找的时候，则认定)=1，(=-1。其他的类似。具体逻辑见代码。

正向反向分别查找之后，取两者的最大值。则这个最大值就是结果。