【Hot100】LeetCode—32. 最长有效括号

---

• 原题链接：32. 最长有效括号

---

1- 思路

题目识别

• 识别1 ：给定一个字符串 s ，求解 s 中的最长有效括号

动态规划

动态规划五部曲

• 递推公式难
• 如果遇到了 s.charAt(i) == ')' 开始递推
• 先求解 preIndex = i - dp[i-1] - 1
  • 保证 preIndex >= 0 && s.charAt(preIndex) == '('
  • dp[i] = 2 + dp[i-1];
  • if(preIndex -1 >= 0) { dp[i] += dp[preIndex-1];}

---

2- 实现

⭐32. 最长有效括号——题解思路

class Solution {public int longestValidParentheses(String s) {int len = s.length();if(len==0){return 0;}int res = 0;// 定义 dp数组// 有效括号长度int[] dp = new int[len];// 递推// preIndex = i - dp[i-1] -1;// if(preIndex >= 0 && s.charAt(preIndex == '('))// dp[i] = 2+dp[i-1];// if(preIndex - 1 >= 0 ) dp[i]+=dp[preIndex-1];// 3.初始化// 4.遍历for(int i = 1 ; i < len ; i++){if(s.charAt(i) == ')'){int pre = i - dp[i-1]-1;if(pre>=0 && s.charAt(pre)=='('){dp[i] = 2 + dp[i-1];if(pre - 1 >=0 ){dp[i] += dp[pre-1];}}}res = Math.max(res,dp[i]);}return res;}
}

---

3- ACM 实现

import java.util.Scanner;public class longestKH {public static int longestS(String str){int len = str.length();// 定义dpint[] dp = new int[len];int res = 0;// 递推// 当前为右括号// 求解 pre = i - dp[i-1] -1;// 如果 pre>=0 && s.charAt(pre) == '('  {dp[i] = 2 + dp[i-1];}// 3. 初始化// 4.遍历for(int i = 1 ; i < len;i++){if(str.charAt(i) == ')'){int preIndex = i - dp[i-1] - 1;if(preIndex>=0 && str.charAt(preIndex) == '('){dp[i] = 2 + dp[i-1];if(preIndex-1>=0){dp[i] += dp[preIndex-1];}}res = Math.max(res,dp[i]);}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();System.out.println("结果是"+longestS(input));}
}