# DP and stack solution in C++, both accepted as best 8ms

• ``````class Solution {
public:
//stack - 8ms;
int longestValidParentheses(string s)
{
int len = s.length(), longest = 0;
if(!len) return 0;
int stack[len]{0}, top = -1;
stack[++top] = -1;
for(int i = 0; i < len; ++i)
{
int t = stack[top];
if(t!=-1 && s[i]==')' && s[t]=='(')
longest = max(longest, i-stack[--top]);
else stack[++top] = i;
}
return longest;
}

//DP - 8ms;
int longestValidParentheses(string s)
{
int len = s.length(), longest = 0;
if(!len) return 0;
int t = 0, maxSub[len]{0};
memset(maxSub, 0, sizeof(int)*len);
for(int i = 0; i < len; ++i)
{
if(i>0 && s[i] == ')')
{
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;
}
};``````

• @LHearen why you can visit stack[-1] and maxSub[-1]?

• @HongXu_1994 You are right on that point, thank you for pointing it out! My mistake here. I've updated it.

But as for the first `stack[-1]` case, there is no chance for that situation since there is a condition before that indexing.

• @LHearen You are right, "++top" not "top++". My mistake.

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