Given a string containing just the characters'('and')', find the length of the longest valid (well-formed) parentheses substring.

For"(()", the longest valid parentheses substring is"()", which has length = 2.

Another example is")()())", where the longest valid parentheses substring is"()()", which has length = 4.

方案1：DP，dp[i]代表从索引i到末尾最长的有效括号组合的长度。

dp[s.length()-1]=0;从后向前逆向求解dp[i]，

1. 如果s[i]=')'，则显然dp[i]=0;
2. 如果s[i]='('，跳过dp[i+1]这段长度从j=i+1+dp[i+1]开始，如果j没越界并且s[j]='0'，正好和s[i]匹配，则dp[i]=dp[i+1]+2；另外此时可能j之后的也可以连上，所以，可能要加上dp[j+1];

public class Solution {    public int longestValidParentheses(String s) {        if (s == null || s.length() < 2)            return 0;        int max = 0;        int[] dp = new int[s.length()];        dp[s.length() - 1] = 0;        for (int i = s.length() - 2; i >= 0; i--) {            char ch = s.charAt(i);            if (ch == '(') {                int j = i + 1 + dp[i + 1];                if (j < s.length() && s.charAt(j) == ')') {                    dp[i] = dp[i + 1] + 2;                    if (j + 1 < s.length())                        dp[i] += dp[j + 1];                }            }            max = Math.max(max, dp[i]);        }        return max;    }    public static void main(String[] args) {        System.out.println(new Solution().longestValidParentheses("(((()(()"));    }}

方案2：stack，时空复杂度都是O(n)。依次遍历字符串中的字符。如果是'（'，压栈索引。如果是'）'，分情况讨论：

1. 如果此时栈为空，表示前面没有需要匹配的或者前面已经计算完毕，'）'不可能作为新的计算开始点，所以更新start为'）'的索引+1.（start 表示当前能构成合法括号组合的起始处）
2. 如果此时栈不空，则出栈，若此时栈为空，则表示当前匹配，更新结果为当前索引-start+1； 若此时不为空，则表示从此时栈顶元素下一位到当前索引是合法的，更新结果为当前索引-栈顶元素索引。

方案2：

import java.util.Stack;public class Solution {    public int longestValidParentheses(String s) {        if (s == null || s.length() < 2)            return 0;        Stack
    
      stack = new Stack
     
      ();        int start = 0;        int max = 0;        for (int i = 0; i < s.length(); i++) {            char ch = s.charAt(i);            if (ch == '(')                stack.push(i);            else {                if (stack.isEmpty())                    start = i + 1;                else {                    stack.pop();                    if (stack.isEmpty())                        max = Math.max(max, i - start + 1);                    else                        max = Math.max(max, i - stack.peek());                }            }        }        return max;    }    public static void main(String[] args) {        System.out.println(new Solution().longestValidParentheses("()()()))(()))("));    }}
     
    

参考：