My DP, O(n) solution without using stack
My solution uses DP. The main idea is as follows: I construct a array longest[], for any longest[i], it stores the longest length of valid parentheses which is 
My solution uses DP. The main idea is as follows: I construct a array <b>longest[]</b>, for any longest[i], it stores the longest length of valid parentheses which is end at i.\n<br>And the DP idea is :\n<br> If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one.\n<br>Else if s[i] is ')'\n<br>\xa0\xa0\xa0\xa0 If s[i-1] is '(', longest[i] = longest[i-2] + 2\n<br>\xa0\xa0\xa0\xa0 Else if s[i-1] is ')' **and s[i-longest[i-1]-1] == '('**, longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]\n<br> For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.\n<br>\n \n\n       int longestValidParentheses(string s) {\n                if(s.length() <= 1) return 0;\n                int curMax = 0;\n                vector<int> longest(s.size(),0);\n                for(int i=1; i < s.length(); i++){\n                    if(s[i] == ')'){\n                        if(s[i-1] == '('){\n                            longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2;\n                            curMax = max(longest[i],curMax);\n                        }\n                        else{ // if s[i-1] == ')', combine the previous length.\n                            if(i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){\n                                longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);\n                                curMax = max(longest[i],curMax);\n                            }\n                        }\n                    }\n                    //else if s[i] == '(', skip it, because longest[i] must be 0\n                }\n                return curMax;\n            }\n\nUpdated: thanks to **Philip0116**, I have a more concise solution(though this is not as readable as the above one, but concise):\n\n    int longestValidParentheses(string s) {\n            if(s.length() <= 1) return 0;\n            int curMax = 0;\n            vector<int> longest(s.size(),0);\n            for(int i=1; i < s.length(); i++){\n                if(s[i] == ')' && i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){\n                        longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0);\n                        curMax = max(longest[i],curMax);\n                }\n            }\n            return curMax;\n        }
['Dynamic Programming']