To explain the thought process, let us define a valid closure of parentheses to be
(...)
, where ...
is either empty or another valid closure.
The ith entry in the DP table, longestEndAt[i]
, represents the length of the longest matching parentheses ending at index i
.
It is easy to see that:

If
s[i] == '('
,longestEndAt[i]
should be 0, since no valid parentheses end with'('
; 
If
s[i] == ')'
, thens[i]
can potentially be an ending parenthesis of a valid closure, or a dangling parenthesis. We need to look at the previous char (if it exists) to find out If
s[i1] == '('
, thens[i]
is the ending parenthesis of closure()
. This closure gives us length 2, but maybe the there were valid parentheses before this closure, and if there is a such a closure, its length islongestEndAt[i2]
. SolongestEndAt[i] = 2 + longestEndAt[i2]
.  If
s[i1] == ')'
, thens[i]
can potentially be an ending parenthesis of closure(...)
where...
is not empty, or it can be a dangling parenthesis. Supposes[i1]
is not a dangling parenthesis, we know the start of the valid parentheses end ats[i1]
is a'('
at indexi1longestEndAt[i1]
, becauselongestEndAt[i1]
denote the length of that sequence (a sequence of valid closures). Let's saystart = i1longestEndAt[i1]
Then, ifs[start1]
is a'('
, we knows[i]
would not be a dangling parenthesis, but an ending parenthesis of a sequence of valid closures starting atstart  1
. If not, thens[i]
is a dangling parenthesis, we can leavelongestEndAt[i]
at0
. SolongestEndAt[i] = 2 + longestEndAt[i1] + longestEndAt[start1]
 If
int longestValidParentheses(string s) {
vector<int> longestEndAt(s.size(), 0);
int longestLen = 0;
for (int i = 1; i < s.size(); i++) {
if (s[i] == ')') {
// To luce's credit we need to perform out of bound error checking (or hacking)
#define longestAt(i) longestEndAt[i < 0 ? 0 : i]
// easy case, just make sure to check if there is a char before s[i1]
if (s[i1] == '(')
longestAt(i) = 2 + longestAt(i2);
// there is a matching '(' at the beginning of the sequence of closures
else if (s[i1longestAt(i1)] == '(')
longestAt(i) = longestAt(i1) + 2 + longestAt(i2longestAt(i1));
// if not, this is a dangling parenthesis, skip it
// update max
longestLen = max(longestLen, longestAt(i));
}
}
return longestLen;
}