题目描述

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

样例

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

算法1

(动态规划) $O(n)$

动态规划四步走
1.确认原问题与子问题: 原问题为求s中最长有效括号，子问题可拆解为前i个中最长有效括号。
2.确认状态: 本题的动态规划状态单一，第i个状态即为前i个字符串中最长括号数。
3.确认边界状态的值: dp[1]=0，从1开始
4.确定状态转移方程: 对于(())适用dp[i] = dp[i - 1] + 2;对于()()适用 dp[i] += dp[i - dp[i]];
两者结合一起判断，防止()()(())这种情况

Java 代码

private int longestValidParentheses(String s) {
        if(s==null || s.equals("")) return 0;
        int maxLen = 0;
        int[] dp = new int[s.length()];
        for (int i=1;i<s.length();i++) {
            if (s.charAt(i) == ')') {
                if (i-dp[i-1]-1 >= 0 && s.charAt(i-dp[i-1]-1)=='(') dp[i] = dp[i-1]+2;
                if (i-dp[i]>=0 && dp[i-dp[i]]>0) dp[i] += dp[i-dp[i]];
            }
            maxLen = Math.max(dp[i],maxLen);
        }
        return maxLen;
    }