一、题目

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

点击查看原题
难度级别： 困难

二、思路

1）动态规划

将格式正确的连续括号子段简称为 ‘有效段’，如果要增加有效段的长度，则有'('+有效段+')'，或 有效段+'()'，这里'()'不能在前面，因为从前向后遍历的时候，已经将其添加如有效段中，本题也就是求解有效段最长长度。
使用dp[i]记忆以s[i]为结尾的有效段长度，根据上述有效段扩展的条件，就可以一次遍历找到最大有效段

三、代码

1）动态规划

  1. class Solution {
  2.     public int longestValidParentheses(String s) {
  3.         int[] dp = new int[s.length()];
  4.         int ans = 0;
  5.         char[] cs = s.toCharArray();
  6.         for (int i = 1; i < cs.length; i++) {
  7.             if(cs[i] == ')') {
  8.                 if (cs[i-1] == '(') {
  9.                     dp[i] = ((i-2) >= 0 ? dp[i-2] : 0) + 2;
  10.                 } else if (i - dp[i-1] >= 1 && cs[i - dp[i-1] - 1] == '(') {
  11.                     dp[i] = dp[i-1] + 2 + (((i - dp[i-1]) >= 2) ?dp[i - dp[i-1] - 2] : 0);
  12.                 }
  13.                 ans = Math.max(dp[i], ans);
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. }

时间复杂度为O(n)，空间复杂度为O(n)