32. Longest Valid Parentheses

We use a stack and dp array to solve the problem where length[i] denotes the max length of valid parenthese which ends at s.charAt(i):

• If s.charAt(i) is '(', length[i] equals to zero;
• If s.charAt(i) is ')', we first judge whether it can form a valid parenthese under the help of stack as what we did in 20. Valid Parentheses. If s.charAt(i) can form a valid parenthese with s.charAt(j), the length of parenthese it can form is i - j + 1. If s.charAt(j - 1) can also form a valid parenthese, then the max length of parenthese that ends at i is i - j + 1 + length[j - 1].

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