题目

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、解题思路

看见最长子串问题,我们可以考虑以i位置为结尾,能扩到最远的距离
在这一题中,我们可以使用这种思路
我们用一个pre变量,记录上一个最长有效括号的最左边界的上一个位置,
当i来到某个位置,有2种情况
1)i位置与pre位置不匹配,dp[i]=0;
2)i位置与pre位置匹配,dp[i]=dp[pre-1]+2

二、代码

class Solution {
    public int longestValidParentheses(String s) {
        char[] cha=s.toCharArray();
        int n=cha.length;
        if(s==null||n<2){
            return 0;
        }
        int res=0;
        int[] dp=new int[n];
        for(int i=1;i<n;i++){
            int pre=i-dp[i-1]-1;
            if(pre>=0&&cha[pre]=='('&&cha[i]==')'){
                dp[i]=dp[i-1]+2+((pre>0)?dp[pre-1]:0);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

总结

看到最长子串问题我们需要想到以i位置结尾或者开头,分析邻近位置与i的关系,推出动态规划公式