动态规划

dp[i]表示以i结尾最长合法字符串。如果s[i]=='('时该字符串一定不合法；当s[i]==')'时，假设存在解，那么该右括号与其对应的左括号之间的字符串一定是合法的。因此对于i-1的位置，以i-1结尾的合法字符串的开头下标为i - dp[i - 1]，当其前一个位置s[i - 1 - dp[i - 1]] == '('时，可以与s[i]进行匹配，dp[i]更新为dp[i - 1] + 2。此时还需要注意，如果在与当前右括号匹配的左括号的前一个位置(i - 1 - dp[i - 1]) - 1，以该处为结尾的最长合法字符串不为0，也需要加到结果上。例如()()。

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestValidParentheses(string s) {
        vector<int> dp(s.size(), 0);
        int maxValue = 0;
        for(int i = 1; i < s.size(); i++) {
            if (s[i] == ')') {
                int prev = i - 1 - dp[i - 1];
                if (prev >= 0 && s[prev] == '('){
                    dp[i] = dp[i - 1] + 2;
                    if (prev - 1 >= 0)
                        dp[i] += dp[prev - 1];
                }
            }
            maxValue = max(maxValue, dp[i]);
        }
        return maxValue;
    }
};