最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
输入: "()(())"
输出: 6
解释: 最长有效括号子串为 "()(())"

解析:dp[i]为以第i个元素结尾的最长有效括号个数。如'('肯定不可能结尾,所以为0。

class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        if(s.length() == 0){
            return 0;
        }
        int ans = 0;
        for(int i=1;i<s.length();i++){
            if(s.charAt(i) == ')'){
                if(s.charAt(i-1) == '('){
                    dp[i] = 2+(i>=2?dp[i-2]:0);
                }
            //((),)为i=2,dp[i-1]表示以i-1结尾有多少有效括号，减去有效括号之后还要有括号才能继续，否则直接肯定为0。之后如果恰好减去有效括号(),前一个正好是(则能进行+操作
            else if((i-dp[i-1]>0)&&s.charAt(i-dp[i-1]-1)=='('){
            //()(()
                    dp[i] = 2+dp[i-1]+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0);
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
}