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;
}
}
