LC32 - 最长有效括号

package DP

func longestValidParentheses(s string) int {
    size := len(s)
    dp := make([]int, size)
    ans := 0
    for i := 1; i < size; i++ {
        if s[i] == '(' {
            // (1) 当前位置为左括号，直接取0
            dp[i] = 0
        } else {
            tmp := dp[i-1]
            if i-1-tmp < 0 || s[i-1-tmp] == ')' {
                // (2) tmp位置不存在或为右括号，直接取0
                dp[i] = 0
            } else {
                // (3) 当前位置的有效括号串长度至少有 2+tmp
                dp[i] = 2 + tmp
                if i-2-tmp >= 0 {
                    // (4) 若i-2-tmp位置存在，则将其对应长度加到当前位置
                    dp[i] += dp[i-2-tmp]
                }
            }
        }
        ans = max(ans, dp[i])
    }
    return ans
}

本题难度相对较大，建议背题，更详细的分析过程参见左神算法讲解。