class Solution {
public int longestValidParentheses(String s) {
    int len = s.length();
    int max = 0;
    int[] longest = new int[len];
    for(int i=1;i<len;i++){
        char c = s.charAt(i);
        if(c == ')'){
            if(s.charAt(i-1)=='('){
                longest[i] = (i>=2?longest[i-2]:0) + 2;
                max = longest[i] > max ? longest[i] :max;
            }else {
                if(i - longest[i-1] - 1>=0 && s.charAt(i - longest[i-1] - 1) == '('){
                    longest[i] = (longest[i-1] + 2) + ((i-longest[i-1]-2)>=0?longest[i-longest[i-1]-2]:0);
                    max = longest[i] > max ? longest[i] :max;
                }
            } 
        }
        
    }
    return max;
}

}