题目描述

给出一个仅包含字符'('和')'的字符串，计算最长的格式正确的括号子串的长度。
对于字符串"(()"来说，最长的格式正确的子串是"()"，长度为2.
再举一个例子：对于字符串")()())",来说，最长的格式正确的子串是"()()"，长度为4.

示例1

输入
"(()"
返回值
2

思路

1. Q1：dp如何设置？
   一开始我设置dp[n+1][n+1],因为这题感觉和回文子串有点想，然而最后发现并不行，看过题解后发现别人设置dp[n+1],dp[i]表示s[:i]的结果。
2. Q2：状态转移方程
   看的别人题解，十分地巧妙，具体可看https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

code

import java.util.*;
public class Solution {
    public int longestValidParentheses (String s) {
        char[] chs = s.toCharArray();
        int n = chs.length;
        if(n==0)return 0;
        int[] dp = new int[n];
        int max=0;
        for(int i=1;i<n;i++){
            if(chs[i]==')'){
                if(chs[i-1]=='(') 
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                else if(i-dp[i-1]>0 && chs[i-dp[i-1]-1]=='('){
                    if(i-dp[i-1]-2>=0)
                        dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2;
                    else
                        dp[i]=dp[i-1]+2;
                }
                max = Math.max(max,dp[i]);
            }
        }
        return max;
    }
}