/**
1. 最长有效的括号字符串 ->  什么样是有效的? 怎么找最长?

2. 什么是有效的括号字符串?
2.1 以(开头, 以)结尾, )的数量等于(
2.2 即: 如果( == 1, ) == -1, 所有前缀和>= 0, 且 总和 == 0;
2.3 合法括号序列的每个(都对应唯一的)

3. 怎么找最长的?
3.1 首先可以把前后两端的非法括号去掉
3.2 指针i 指向合法序列的开头, 指针j指向遍历所有字符, cnt统计当前前缀和 , 当前j指向( 时++, 否则 --;
3.3 根据前缀和cnt的情况:
    3.3.1 当 cnt == 0 时, 说明构成了一个合法序列,       更新结果        -> 总和 == 0
    3.3.2 当 cnt <  0 时, 说明从i开始的序列必定非法,    更新i = j + 1   -> 合法括号序列的每个"("都对应唯一的")"
    3.3.3 当 cnt >  0 时, 说明还需要继续扩展寻找对应的), 无需处理        -> 所有前缀和>= 0

3.4 这种处理方式只能处理 存在 cnt == 0 和cnt < 0 的时候, 像 ((() 这种就无法更新结果集了, 因为括号是对称的, 所以可以翻转过来再计算一次, 取最大值

*/

/**
1. 动态规划: 一个有效的括号序列(开头, 以)结尾, )的数量等于(, 且去除左右两端的括号后,要么是空字符串, 要么必定也是一个有效的括号序列
1.1 状态定义: f[i] 是以 i 结尾的最长有效子序列的长度
    1.1.1: 无后效性:    可以只通过i之前的结果求出f[i]
    1.1.2: 最优子结构:  i结尾的最长子序列的子集必定是一个有效序列
1.2 状态计算: 括号序列必定以) 结尾, 考虑 ) 前一个字符的情况:
    1.2.1 s[i-1] == '(', s[i] 可以与 s[i-1] 匹配, 把() 追加到s[i-2] 上去,  f[i] = f[i-1] + 2 + f[i-2]
    1.2.2 s[i-1] == ')', s[i] 可以尝试与之前某个(匹配, 中间的长度为f[i-1], 所以待匹配的(的位置为prev =  i - f[i-1] - 1
                            即可以把整个prev ~ i的序列追加到s[prev-1]上去, f[i] = f[i-1] + f[i - f[i-1] - 2] + 2
1.3 边界: f[~] = 0

*/

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;
        return dp(s);
        // return doublePoint(s);
    }

    public int dp(String s){
        int n = s.length();
        int[] f = new int[n];
        for (int i = 1; i < n ; i++ ){
            if (s.charAt(i) == '(') continue;
            if (s.charAt(i-1) == '(') f[i] = (i >= 2 ? f[i-2] : 0) + 2;
            else{
                int prev = i - f[i-1] - 1;
                if (prev >= 0 && s.charAt(prev) == '(') f[i] = f[i-1] + 2 + (prev-1 >= 0 ? f[prev - 1] : 0);
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }

    public int doublePoint(String s){
        char[] str = s.toCharArray();
        int result = calc(str);
        return Math.max(result, calc(reverse(str)));
    }

    public char[] reverse(char[] str){
        int l = 0 , r = str.length -1 ;
        while (l < r){
            char t = str[l];
            str[l++] = str[r];
            str[r--] = t;
        }

        for (int i = 0 ; i < str.length ; i++){
            if (str[i] == '(')  str[i] = ')';
            else                str[i] = '(';
        }
        return str;
    }

    int calc(char[] str){
        int l = 0, r = str.length-1;
        while(l < str.length && str[l] != '(') l++;
        while(0 <= r && str[r] != ')') r--;
        if (r <= l) return 0;

        int res = 0;
        for(int i = l, j = l, cnt = 0;i <= r && j <= r ; j++){
            if (str[j] == '(')  cnt ++ ;
            else                cnt --;

            if (cnt ==  0) {
                res = Math.max(res, j - i + 1);
            } else if (cnt < 0){
                i = j+1;
                cnt = 0;
            }
        }
        return res;
    }
}