32. 最长有效括号

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

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

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

示例 3：
输入：s = ""
输出：0

题目分析

显然，该问题满足最优子结构特性，因此可以采用动态规划方法求解。令\(dp[i]\)表示以下标为\(i\)结尾的字符串（之所以这样设计状态，是为了满足无后效性），初始时\(dp\)数组全部赋值为0。
接下来考虑状态转移方程：由题意可知，若字符串以"("结尾，那必然是格式不正确的字符串，故长度为0，因此只需要考虑以")"结尾的字符串。
如果\(s[i]=')' \&\& s[i - 1]='('\)，即字符串形如\(...()\)，那么\(dp[i]=dp[i-2]+2\)，
如果\(s[i]=')' \&\& s[i - 1]=')'\)，即字符串形如\(...))\)，那么需要再进行一步判断，即如果\(s[i-dp[i-1]-1]='('\)，那么这就是一个合法的字符串。但是进行状态转移时需要注意到直接连接在该字符串之前的合法字符串，也要将其的长度给加上，即\(dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]\)。
代码如下：

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        int n = s.size();
        vector<int> dp(n, 0);
        for (int i = 1; i < n; i++) 
        {
            if (s[i] == ')') 
            {
                if (s[i - 1] == '(') 
                {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } 
                else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') 
                {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }
};

时间复杂度\(O(n)\)，空间复杂度\(O(n)\)