力扣hot100 最长有效括号 动态规划

Problem: 32. 最长有效括号

思路

👨‍🏫 参考题解

Code

⏰ 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

class Solution {public int longestValidParentheses(String s){int n = s.length();int[] f = new int[n];// f[i] 表示以第 i 个字符结尾的最长有效子字符串的长度int ans = 0;for (int i = 1; i < n; i++){if (s.charAt(i) == ')')// 只有右括号结尾才有效if (s.charAt(i - 1) == '(')// 上一个是 左括号{if (i < 2)f[i] = 2;elsef[i] = f[i - 2] + 2;} else // 上一个也是 右括号{if (f[i - 1] > 0) //前面已经组成有效括号对序列{int pre = i - 1 - f[i - 1]; // 此处 s[pre] 与 s[i] 是相配对的位置if (pre >= 0 && s.charAt(pre) == '(')// 存在且配对成功{f[i] = f[i - 1] + 2;// 在前边的 f[i-1] 上再加上一对if (pre - 1 > 0)//看看 pre 前边是否还有已经配对好的序列f[i] += f[pre - 1];}}}ans = Math.max(ans, f[i]);//更新答案}return ans;}
}