32.最长有效括号

/*
 * @lc app=leetcode.cn id=32 lang=typescript
 *
 * [32] 最长有效括号
 */

// @lc code=start
function longestValidParentheses(s: string): number {
	// 遇到左括号为0
	if (s.length == 0) return 0;
	let dp = Array.from({ length: s.length }, () => 0);
	let pre = 0;
	let ans = 0;
	// 索引0位置肯定为0
	for (let i = 1; i < s.length; i++) {
		if (s[i] === ")") {
			// 找到dp[i-1]前一个位置，即尝试找到符合的"("索引位置
			pre = i - dp[i - 1] - 1;
			if (pre >= 0 && s[pre] === "(") {
				let preVal = dp[pre - 1] ?? 0;
				// 计算出dp[i]
				// dp[i] 表示以索引 i 结尾的最长有效括号子串的长度。
				dp[i] = dp[i - 1] + preVal + 2;
			}
		}
		ans = Math.max(ans, dp[i]);
	}
	return ans;
}

console.log(longestValidParentheses("()(())"));

// @lc code=end