JAVA练习275-乘积最大子数组

题目概览

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

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如"(()())"。

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i]为'('或')'

来源：32. 最长有效括号 - 力扣（LeetCode）

解题分析

方法：动态规划

用 dp 存储结果，分情况而论：
1. 当 s[ i ] 为 ' ( ' 且 s[ i - 1 ] 为')' 时，dp[i]至少为2，需要看 i - 2 是否连上了即看 dp[i - 2]，可得 dp[i] = dp[i-2] + 2；
2. 当 s[ i ] 为 ' ) ' 且 s[ i - 1 ] 为')' 时，dp[i]得看前面差 dp[i-1] 长度是否有 '('，即当 i - dp[i - 1] - 1 >= 0 且 s[i - dp[i - 1] - 1] == '(' 时，dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2 （加上 dp[i-dp[i-1]-2] 是因为有连着的情况）

时间复杂度: O(n)
空间复杂度: O(n)

class Solution { public int longestValidParentheses(String s) { char[] cs = s.toCharArray(); if (cs.length <= 1) { return 0; } int[] dp = new int[cs.length + 1]; int longest = 0; for (int i = 1; i < cs.length; ++i) { if (cs[i] == ')' && cs[i - 1] == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else if (cs[i] == ')' && cs[i - 1] == ')' && i - dp[i - 1] > 0 && cs[i - dp[i - 1] - 1] == '(') { dp[i] = dp[i - 1] + ((i - dp[i - 1]) > 2 ? dp[i - dp[i - 1] - 2]: 0) + 2; } longest = Math.max(longest, dp[i]); } return longest; } }