题目: 给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例 1: 输入:s = “(()” 输出:2 解释:最长有效括号子串是 “()” 示例 2: 输入:s = “)()())” 输出:4 解释:最长有效括号子串是 “()()” 示例 3: 输入:s = “” 输出:0 提示: 0 <= s.length <= 3 * 104 si 为 ‘(’ 或 ‘)’ 思路: 看到最长这个子牙,可以考虑尝试使用动态规划进行分析。这是一个最值型动态规划的题目。 动态规划分析的4个步骤:
1、确定状态
public class Solution {
private int longestValidParentheses(String s) {
char[] chars = s.toCharArray();
int size = chars.length;
int[] dp = new int[size];
int maxVal = 0;
for (int i = 1; i < size; i++) {
if (chars[i] == ')') {
if (chars[i - 1] == '(') {
dp[i] = 2;
if (i - 2 > 0) {
dp[i] = dp[i] + dp[i - 2];
}
} else if (dp[i - 1] > 0) {
if ((i - dp[i - 1] - 1) >= 0 && chars[i - dp[i - 1] - 1] == '(') {
dp[i] = dp[i - 1] + 2;
if ((i - dp[i - 1] - 2) >= 0) {
dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
}
}
}
}
maxVal = Math.max(maxVal, dp[i]);
}
return maxVal;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = ")()())";
int result = solution.longestValidParentheses(s);
System.out.println("result = " + result);
}
}
链接:https://leetcode-cn.com/problems/longest-valid-parentheses