// f[i][j] 表示i，j的最长子序列，但是需要很多判断 复杂度又是pow（n ， 3） 可能会超时

 //  （（）
 // f(0,0,2)  前面括号刚好匹配
 //  ( ( ( ) ) ) 
 // f(0,0,0,2,4,6)  和前面的前面匹配括号
 //  （）（）
 // f(0,2,0,4) 前面有一组匹配的

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n < 2) return 0; // 空串或长度1直接返回0
        vector<int> f(n, 0);
        int maxlen = 0;
        for (int i = 1; i < n; ++i) {
            if (s[i] == ')') { // 只有右括号可能作为有效子串结尾
                // 情况1：与前一个字符形成"()"
                if (s[i-1] == '(') {
                    // 若i-2 >=0，则加上之前的有效长度，否则直接为2
                    f[i] = (i >= 2) ? f[i-2] + 2 : 2;
                }
                // 情况2：前一个字符是')'，尝试匹配更左侧的'('
                else if (i - f[i-1] - 1 >= 0 && s[i - f[i-1] - 1] == '(') {
                    // 加上中间有效长度 + 新匹配的2 + 左侧可能的有效长度
                    int prev = (i - f[i-1] - 2 >= 0) ? f[i - f[i-1] - 2] : 0;
                    f[i] = f[i-1] + 2 + prev;
                }
                // 更新最大长度
                maxlen = max(maxlen, f[i]);
            }
        }
        return maxlen;
    }
};

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxlen = 0, n = s.length();
        vector<int> dp(n, 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] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxlen = max(maxans, dp[i]);
            }
        }
        return maxlen;
    }
};