Very direct DP solution, clean and efficient besides it's beautifully explained

• Searching for the equation is always the key in DP problem, in this problem we are about to suppose the longest till the `current`,

maxSub[len] = {0};

always stick this in mind before reading the following code.

Once we encounter a closing bracket `)` then we check its previous `longest` valid parentheses and try to find its corresponding open bracket `(`

int t = i-maxSub[i-1]

to check whether there is a `corresponding` open bracket `(`

if(t>0 && s[t-1] == '(')

if there is, then we should retrieve the `longest` for the current closing bracket `)`

maxSub[i] = (t>1? maxSub[t-2] : 0)+maxSub[i-1]+2;

at last, we update the global longest and there.

We're done the job easily and beautifully.

``````class Solution {
public:
int longestValidParentheses(string s)
{
int len = s.length(), longest = 0;
if(!len) return 0;
int maxSub[len] = {0};
for(int i = 0; i < len; ++i)
{
if(s[i] == ')')
{
int t = i-maxSub[i-1];
if(t>0 && s[t-1] == '(') maxSub[i] = (t>1? maxSub[t-2] : 0)+maxSub[i-1]+2;
longest = max(longest, maxSub[i]);
}
}
return longest;
}
};
``````

• int t = i - maxSub[i-1]
will cause maxSub[-1] if i == 0 and you can start from i = 1.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.