最长括号匹配问题

问题描述

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

解题

两种情况：...()与((...))
使用dp[i]表示以s[i]结尾的最长有效括号串的长度

// ...()
dp[i] = dp[i - 2] + 2;
// ...((...))
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];