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.

Solution 1: 栈存的是index，不是括号。如果是(，压入index到栈；如果是)，若栈顶元素是(，则弹出，否则压入)的index。最后栈中留下的是不配对的index，扫描整个栈，找出这些index间夹着的配对最长长度

    public int longestValidParentheses(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        LinkedList<Integer> stack = new LinkedList<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);        
            if (c == '(') {
                stack.offerLast(i);   
            } else {
                if (stack.isEmpty() || s.charAt(stack.peekLast()) != '(') {
                    stack.offerLast(i);
                } else {
                    stack.pollLast();
                }
            }

        }
        if (stack.isEmpty()) {
            return s.length();
        }
        int max = 0, cur = s.length();
        while (!stack.isEmpty()) {
            int index = stack.pollLast();
            max = Math.max(cur - index - 1, max);
            cur = index;
        }
        max = Math.max(cur, max);
        return max;
    }

better way:

    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int max=0;
        int left = -1;
        for(int j=0;j<s.length();j++){
            if(s.charAt(j)=='(') stack.push(j);            
            else {
                if (stack.isEmpty()) left=j;
                else{
                    stack.pop();
                    if(stack.isEmpty()) max=Math.max(max,j-left);
                    else max=Math.max(max,j-stack.peek());
                }
            }
        }
        return max;
    }

or:

The idea is simple, we only update the result (max) when we find a "pair".

If we find a pair. We throw this pair away and see how big the gap is between current and previous invalid.

EX: "( )( )" stack: -1, 0,

when we get to index 1 ")", the peek is "(" so we pop it out and see what's before "(".

In this example it's -1. So the gap is "current_index" - (-1) = 2.

The idea only update the result (max) when we find a "pair" and push -1 to stack first covered all edge cases.

    public int longestValidParentheses(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        int result = 0;
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
                stack.pop();
                result = Math.max(result, i - stack.peek());
            } else {
                stack.push(i);
            }
        }
        return result;
    }

Solution 2: DP

longest[i], it stores the longest length of valid parentheses which is end at i.

If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.

Else if s[i] is ')'

 If s\[i-1\] is '\(', longest\[i\] = longest\[i-2\] + 2 \(其实这种情况包含在下面的情况\)

 Else if s\[i-1\] is '\)' **and s\[i-longest\[i-1\]-1\] == '\('**, longest\[i\] = longest\[i-1\] + 2 + longest\[i-longest\[i-1\]-2\]

For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.

            if(s.length() <= 1) return 0;
            int curMax = 0;
            vector<int> longest(s.size(),0);
            for(int i=1; i < s.length(); i++){
                if(s[i] == ')'){
                    if(s[i-1] == '('){
                        longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2;
                        curMax = max(longest[i],curMax);
                    }
                    else{ // if s[i-1] == ')', combine the previous length.
                        if(i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){
                            longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);
                            curMax = max(longest[i],curMax);
                        }
                    }
                }
                //else if s[i] == '(', skip it, because longest[i] must be 0
            }
            return curMax;