leetcode热题100学习计划-动态规划-32最长有效括号

题目

32最长有效括号

思路

使用动态规划去做，令dp[i]为以i为结尾最长有效子串的长度，可得递推关系如下

代码

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        char[] array=s.toCharArray();
        int n=array.length;
        int[] dp = new int[n];
        
        for (int i = 1; i < n; i++) {
            if (array[i] == ')') {
                if (array[i - 1] == '(') {
                    if(i>=2){
                        dp[i]=dp[i-2]+2;
                    }else{
                        dp[i]=2;
                    }
                  
                } else if (i - dp[i - 1] > 0 && array[i - dp[i - 1] - 1] == '(') {
                    //第一个条件，保证不越界
                    //第二个条件，上一个符合要求的子串的前面应该是'('
                    if(i-dp[i-1]>=2){
                        //如果比2大，说明上上一个子串存在，即dp[i-dp[i-1]-2]存在
                        dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2;
                    }else{
                        //上上一个子串不存在，直接加过来
                        dp[i]=dp[i - 1] +2;
                    }
                   
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

原文地址：https://blog.csdn.net/qq_42445647/article/details/136474048

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！