leetcode_32

Golang:

思路：动态规划，这题用二维数组也可以解，但不能通过所有测试用例，所以要用一维的

代码如下：

func longestValidParentheses(s string) int {
    res:=0
    arr:=make([]int,len(s))
    for i:=0;i<len(s);i++{
        if s[i]==')'{
            if i-1>=0 {
                if s[i-1]=='(' {
                    if i-2>=0 {
                        arr[i]=arr[i-2]+2
                    }else{
                        arr[i]=2
                    }
                }else{
                    if i-arr[i-1]-1>=0&&arr[i-1]>0&&s[i-arr[i-1]-1]=='('{
                        if i-arr[i-1]-2>=0{
                            arr[i]=arr[i-1]+2+arr[i-arr[i-1]-2]
                        }else{
                            arr[i]=arr[i-1]+2
                        }
                    }
                }
                if arr[i]>res {
                    res=arr[i]
                }
            }
        }
    }
    return res
}

有疑问加站长微信联系（非本文作者）