代码随想录算法训练营第五十六天 | 1143. 最长公共子序列 & 1035.不相交的线 & 53. 最大子数组和

1. 最长公共子序列

1143. 最长公共子序列 - 力扣(LeetCode)

最长公共子数组必须连续,所以一旦元素不相等,当前的最长公共长度不能由前面得来,只能为0

而最长公共子序列,可以断开,所以不相等时,它的长度可以从前面的状态获取(取最大)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // dp[i][j] 
        int l1 = text1.length();
        int l2 = text2.length();
        // 第一行第一列预留出来,防止 -1 oob
        int[][] dp = new int[l1 + 1][l2 + 1];

        // 从第二行第二列开始
        for(int i = 1; i < l1 + 1; i++){
            for(int j = 1; j < l2 + 1; j++){
                // 记得序号 -1 
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    // 不相等时,去掉一个,看哪边更大
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[l1][l2];
    }
}

2. 不相交的线

1035. 不相交的线 - 力扣(LeetCode)

本质就是求最长公共子序列

3. 最大子数组和

53. 最大子数组和 - 力扣(LeetCode)

前一位如果小于0,那加上前一位只会更小,所以不加

class Solution {
    public int maxSubArray(int[] nums) {
        int l = nums.length;
        int[] dp = new int[l]; // dp[i] 0 - i 的最大子数组和

        dp[0] = nums[0];
        int max = dp[0];
        for(int i = 1; i < l; i++){
            // 前一位如果小于0,那加上前一位只会更小,所以不加
            dp[i] = Math.max(dp[i-1], 0) + nums[i];
            max = Math.max(dp[i], max);
        }

        return max;
    }
}

文章来源地址https://www.uudwc.com/A/pjwzr/

原文地址:https://blog.csdn.net/weixin_50815909/article/details/133512433

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年10月28日 22:39
在vite中使用react-router-dom-v6 路由报错 Uncaught SyntaxError: Unexpected token ‘<‘
下一篇 2023年10月28日 23:39