Pure 1D-DP without using stack (python) with detailed explanation
class Solution(object):\n        def longestValidParentheses(self, s):\n            """\n            :type s: str\n            :rtype: int\n            """\n   
    class Solution(object):\n        def longestValidParentheses(self, s):\n            """\n            :type s: str\n            :rtype: int\n            """\n            # use 1D DP\n            # dp[i] records the longestValidParenthese EXACTLY ENDING at s[i]\n            dp = [0 for x in xrange(len(s))]\n            max_to_now = 0\n            for i in xrange(1,len(s)):\n                if s[i] == ')':\n                    # case 1: ()()\n                    if s[i-1] == '(':\n                        # add nearest parentheses pairs + 2\n                        dp[i] = dp[i-2] + 2\n                    # case 2: (()) \n                    # i-dp[i-1]-1 is the index of last "(" not paired until this ")"\n                    elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':\n                        if dp[i-1] > 0: # content within current matching pair is valid \n                        # add nearest parentheses pairs + 2 + parentheses before last "("\n                            dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]\n                        else:\n                        # otherwise is 0\n                            dp[i] = 0\n                    max_to_now = max(max_to_now, dp[i])\n            return max_to_now
['Dynamic Programming', 'Python']