题解 | 最长的括号子串

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
public int longestValidParentheses(String s) {
    int n = s.length();
    int[] dp = new int[n];
    int max = 0;

    for (int i = 1; i < n; i++) {
        if (s.charAt(i) == ')') {
            // 情况 1："...()"
            if (s.charAt(i - 1) == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            }
            // 情况 2："...))"
            else {
                int j = i - dp[i - 1] - 1;
                if (j >= 0 && s.charAt(j) == '(') {
                    dp[i] = dp[i - 1] + 2 + (j > 0 ? dp[j - 1] : 0);
                }
            }
            max = Math.max(max, dp[i]);
        }
    }
    return max;
}

}

大循环无视掉“（”，直接从“）”开始找，因为只有“）”能闭合一个合法“（）”，分两种情况：

第一种：“（）”类型，那就记录“（）”之前的紧挨着的最长的合法“（）”的长度 + 当前的“（）”的长度：dp[i - 2] + 2;

第二种：“。。（）（）（））”类型，那就根据当前位置: i , 往前找紧挨着的最长的合法“（）”的长度： dp[i - 1], 然后再往前倒一位： -1:

int j = i - dp[i - 1] - 1

看dp[j]是不是“（”，如果是，说明是“。。（（）（）（））”这种情况，那就记录 紧挨着的最长的合法“（）”的长度 + 当前的“（）”的长度 + j这个位置之前一位记载的最长的长度，因为可能是“（）（（）（）（））”这种情况：

dp[i] = dp[i - 1] + 2 + (j > 0 ? dp[j - 1] : 0);

其他情况都是无法闭合的状态，因为max已经记录了当前位置的最长的连续的长度，dp已经记录了之前出现过的每个位置能出现的最长的连续长度，所以可以直接略过。