lc32. 最长有效括号（dp）

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：

输入：s = “”
输出：0

提示：

0 <= s.length <= 3 * 104
s[i] 为 ‘(‘ 或 ‘)’

class Solution {
    /**
    f[i]表示以i下标为结尾的最大长度
    s[i] = '(' f[i] = 0
    s[i] = ')' {
        s[i-1] = '(' f[i] = 2 + f[i - 2]
        s[i-1] = ')' 判断s[i - f[i-1] - 1] == '(' 
    }
     */
    public int longestValidParentheses(String s) {
        char[] ch = s.toCharArray();
        int n = ch.length;
        int[] f = new int[n + 1];
        f[0] = 0;
        int res = 0;
        for (int i = 1; i < n; ++i) {
            //ch[i] == '(' 时 f[i] = 0;
            if (ch[i] == ')') {
                if (ch[i - 1] == '(') {
                    f[i] = 2;
                    if (i > 1) f[i] += f[i - 2];
                }
                else if (f[i - 1] > 0 && i - f[i - 1] - 1 >= 0) {
                    //f[i - 1] > 0 必须保证ch[i - 1]这个括号是有效的
                    if (ch[i - f[i - 1] - 1] == '(') {
                        f[i] = f[i - 1] + 2;
                        //加上之前的部分
                        if (i - f[i - 1] - 2 >= 0)
                            f[i] += f[i - f[i - 1] - 2]; 
                    } 
                }
            }
            res = Math.max(res, f[i]);
        }
        return res;
    }
}