```
1. dp[i] = {max(k) | s[i-k+1, i] is well formed. k=0 means empty}
2. For char s[i], we should check the char s[i-1-dp[i-1]].
If s[i] and s[i-1-dp[i-1]] are matched, substring from i-1-dp[i-1] to i is well formed.
Then, we should joint it with previous well formed substring which ends at s[i-1-dp[i-1]-1].
int longestValidParentheses(string s) {
vector<int> dp(s.length(),0);
int res = 0;
for(int i=1; i<s.length(); ++i)
if(s[i]==')' && i-1-dp[i-1]>=0 &&s[i-1-dp[i-1]]=='('){
if(i-1-dp[i-1]-1 >= 0) dp[i]= dp[i-1]+2+dp[i-1-dp[i-1]-1];
else dp[i]= dp[i-1]+2;
res = max(res, dp[i]);
}
return res;
}
```