LeetCode_32 最长有效括号

题目描述：

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

示例 1:

输入: “(()”

输出: 2

解释: 最长有效括号子串为 “()”

示例 2:

输入: “)()())”

输出: 4

解释: 最长有效括号子串为 “()()”

class Solution {
public:
    int longestValidParentheses(string s) {
        //dp[i]:到i字符(含)为止，有效的字符长度
        if(s.size()<2)
            return 0;
        int n=s.size();
        vector<int> dp(n,0);
        int max_len=0;
        for(int i=1;i<n;i++){
            if(s[i]==')'){
                if(s[i-1]=='(')
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                else if(i-dp[i-1]-1>=0&&s[i-1-dp[i-1]]=='('){//下标不越界并且子数组对应的括号是'('
                    dp[i]=dp[i-1]+2+(i-dp[i-1]-1>0?dp[i-2-dp[i-1]]:0);
                }
            }
            max_len=max(max_len,dp[i]);
        }
        return max_len;
    }
};