32. Longest Valid Parentheses

using dynamic programming 
***
s=’（（）（（））’
dp[7]=以s[6]为结尾的longest valid parentheses substring 长度
j=7-2-dp[6]=5-2=3
j>0 and s[3]=’(‘
d[7]=d[6]+2+d[3]=2+2+2=6

s=’（（）)（））’
j=7-2-dp[6]=5-2=3
s[3]!=’(‘
d[7]=0
****


class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s)==0:
            return 0
        max_len=0
        dp=[0]*(len(s)+1)
        for i in range(1,len(s)+1):
            if s[i-1]=='(':
                dp[i]=0
            else:
                j=i-2-dp[i-1]
                if j>=0 and s[j]=='(':
                    dp[i]=dp[i-1]+2+dp[j]
                    max_len=max(max_len,dp[i])
                else:
                    dp[i]=0
                
        return max_len

using stack 

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack=[]
        start=0
        max_length=0
    
        for i in range(len(s)):
            if s[i]=='(':
                stack.append(i)
                
            elif s[i]==')':
                if len(stack)==0:
                    start=i+1
                else:
                    stack.pop()
                    if len(stack)==0:
                        max_length=max(max_length,i-start+1)
                        
                    else: 
                        max_length=max(max_length,i-stack[-1])


        return max_length