0032.最长有效括号

https://leetcode.cn/problems/longest-valid-parentheses/

方法一：动态规划

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

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