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

题目概览给你一个只包含(和)的字符串找出最长有效格式正确且连续括号 子串 的长度。左右括号匹配即每个左括号都有对应的右括号将其闭合的字符串是格式正确的比如(()())。示例 1输入s (()输出2解释最长有效括号子串是 ()示例 2输入s )()())输出4解释最长有效括号子串是 ()()示例 3输入s 输出0提示0 s.length 3 * 104s[i]为(或)来源32. 最长有效括号 - 力扣LeetCode解题分析方法动态规划用 dp 存储结果分情况而论1. 当 s[ i ] 为 ( 且 s[ i - 1 ] 为) 时dp[i]至少为2需要看 i - 2 是否连上了即看 dp[i - 2]可得 dp[i] dp[i-2] 22. 当 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; } }