32.最长有效括号(序列dp)

链接：32. 最长有效括号 - 力扣（LeetCode）

题解：

class Solution { public: int longestValidParentheses(string s) { int len = s.size(); if (len == 0) { return 0; } // 以下表i为结尾的最长匹配 vector<int> dp(s.size(), 0); int result = 0; for (int i = 1; i < s.size(); ++i) { if (s[i] == ')') { // 如果当前是(，dp[i-2] + 2 ‘（’前面那个位置的最长加上当前的2个 if (s[i - 1] == '(') { dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2; } else { // s[i-1]位置最长的匹配的前一个字放如果是'(' // (前面的最长匹配也需要加上 dp[i-[dp[i-1]-2] + dp[i-1] + 2; if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') { dp[i] = (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2; } } } result = max(dp[i], result); } return result; } };