最长有效括号（复习重点）

题目

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

示例 1:

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

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

解题思路

精疲力尽....连续10个小时，最后还是抄了题解，找转移方程真是太费劲了，自己的解法总是遇到无穷无尽的边界判断，脑子要炸了。

代码

class Solution {
    public int longestValidParentheses(String s) {
        int maxLength = 0;
        int dp[] = new int [s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')'){
                if (s.charAt(i - 1) == '('){ //上一个括号可以和当前形成组合
                    dp[i] = ( i >= 2 ? dp[i - 2] : 0) +2;
                }else if(i - 1 - dp[i - 1] >= 0 && s.charAt(i - 1 - dp[i - 1]) == '('){ //排除掉已经计算过的括号后，再判断前一个括号是否可以和当前形成组合，dp[i - 1]代表上一步中已经得知的有效括号长度，减去这个长度后就可方便的得到尚未匹配的那个括号。
                    dp[i] = dp[i - 1] + ((i -2 - dp[i - 1]) >= 0 ? dp[i -2 - dp[i - 1]]:0)  + 2 ;
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }
}