Longest Valid Parentheses

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.

Use a stack to record the index of left parenthese:

1. ')))' case - keep changing lastValidIndex
2. '()()' case - calculate length lastValidIndex to current index
3. '(()()' case - calulate length top index in stack + 1 to current index

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

        Stack<Integer> stack = new Stack<Integer>();
        int lastValidIndex = 0;
        int maxLength = 0;

        char[] pArray = s.toCharArray();

        for (int i=0; i<pArray.length; i++) {
            char curr = pArray[i];
            if (curr=='(') {
                stack.push(i);
            } else {
                //)))) case
                if (stack.isEmpty()) {
                    lastValidIndex = i+1;
                } else {
                    stack.pop();
                    // () or (()) case, last ) in the string, you always need to start calculate from the lastValidIndex 
                    if (stack.isEmpty()) {
                        maxLength = Math.max(maxLength, i-lastValidIndex+1);
                    // (()() the second last ) in the string, you need to calculate from the top element in the stack
                    } else {
                        maxLength = Math.max(maxLength, i-stack.peek());
                    }
                }
            }
        }
        return maxLength;
    }