法一：一维dp

• 子串必须连续
• 这种涉及子串的，立马要想到

  以 i 结尾

• 以 i 结尾，往左推最多推多长有效？
  • i 位置是 (
  • i 位置是 ）
    • 看i - 1 位置的答案, 比如是4， 那么我就看i - 5的字符
      • 如果i - 5位置是 ( , 那么 i 位置的答案至少是6， 然后再看 i - 6结尾的答案能不能跟你续上

• 往前跳着看一遍 (看5位置)就够了，下面说明为什么
  • 
  • 
  • 
  • 
  • 现在知道为什么 到 i 位置的时候， 只需要往左边看一遍就行了吧， 因为都是累加过来的

    public int longestValidParentheses(String s) {
    int[] dp = new int[s.length()];
    int pre = 0;
    int res = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            // pre是当前位置的）， 应该找哪个位置的左括号
            pre = i - dp[i - 1] - 1;
            if (pre >= 0 && s.charAt(pre) == '(') {
                dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;  
    }

    法二：栈

    、

    public int longestValidParentheses2(String s) {
       int max = 0;
       //栈里存的是下标
       Stack<Integer> stack = new Stack<>();
       // 栈底始终要维持一个含义：「最后一个没有被匹配的右括号的下标」
       stack.push(-1);
       for (int i = 0; i < s.length(); i++) {
           if (s.charAt(i) == '(') {
               stack.push(i);
           } else { // ')'
               stack.pop();
               if (stack.isEmpty()) {
                   stack.push(i);
               } else {
                   max = Math.max(max, i - stack.peek());
               }
           }
       }
       return max;
    }