[LeetCode] 32. 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.

1. The tricky part of this problem is it looks like a greedy solvable problem, however it is not. (Maybe). While when you start to think about dp, 1-d dp is usually not the first intuition. The property of a valid parentheses chunk, (each valid chunk should be composed 2 or more valid sub chunks, either inside or side by side). is the key. 

public class Solution {
    public int longestValidParentheses(String s) {
        
        // 1d dp
        
        int len = s.length();
        
        if(2 > len)
            return 0;
            
        int[] dp = new int[len];
        
        for(int i = 0; i < len; ++i){
            dp[i] = -1;
        }
        
        dp[0] = 0;
        
        if(s.charAt(0) == '(' && s.charAt(1) == ')' )
        {
            dp[1] = 2;
        }
        else{
            dp[1] = 0;
        }
        
        for(int i = 2; i < len; ++i){
            if(s.charAt(i) == '(')
                dp[i] = 0;
            else{
                if(0 == dp[i-1]){
                    if('(' == s.charAt(i-1))
                        dp[i] = dp[i-2]+2;
                    else{
                        // ')' at i-1
                        dp[i] = 0;
                    }
                }else{
                    // if dp[i-1] != 0
                    int l = dp[i-1];
                    if(i - l - 1 >=0 && '(' == s.charAt(i - l - 1)){
                        // wrong answer: ()(())
                        int pre = 0;
                        if(i-l-2>=0){
                            pre = dp[i-l-2];
                        }
                        dp[i] = pre + l + 2;
                    }
                    else{
                        dp[i] = 0;
                    }
                }
            }
        }
        
        int max = dp[0];
        for(int i = 0; i < len; ++i){
            max = Math.max(dp[i], max);
        }
        
        return max;

    }
}