力扣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;
					else
						f[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;
	}
}