代码随想录第五十三天|最长公共子序列、最大子数组

Leetcode 1143. 最长公共子序列

题目链接: 最长公共子序列
自己的思路:没想出来！！！

正确思路:首先这道题由于是涉及到了两个数组（或字符串），所以我们要使用二维dp数组来表示；动规五部曲：1、dp数组的含义：dp[i][j]表示以text1[i-1]和text2[j-1]结尾的最长公共子序列的长度（这里为什么是i-1和j-1前面一些题解已经解释了）；2、递推公式：dp[i][j]是和三个数组有关系的，分别是dp[i-1][j-1]、dp[i][j-1]和dp[i-1][j]，这里就要分情况了，因为我们要判断当前的元素要不要归到最长公共子序列里面去，所以要判断text1[i-1]和text2[j-1]是否相等，如果相等的话，就要在dp[i-1][j-1]基础上加1，如果不相等的话，就要对另外两个求最大值，因为我们的dp[i][j]其实是可以和dp[i][j-1]有关的，我们可以忽略掉text[i-1]这个元素，因为现在text1[i-1]和text2[j-1]并不相等，另一个也是如此！！！3、dp数组的初始化：这里还是和之前那道题一样，全部初始化为0，解释看之前的题；4、遍历顺序：由于dp[i][j]是由前面的数来决定的，所以我们是从前向后遍历；5、打印dp数组：主要用于debug！！！！！

代码:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        //转数组，方便操作
        char[] c1 = text1.toCharArray();
        char[] c2 = text2.toCharArray();
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 1;i<=m;i++){
            for (int j = 1;j<=n;j++){
                //递推公式
                if (c1[i-1]==c2[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[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Leetcode 1035. 不相交的线

题目链接: 不相交的线
自己的思路:和上一个题一模一样！！！！！

正确思路:

代码:

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m+1][n+1];
        for (int i=1;i<=m;i++){
            for (int j = 1;j<=n;j++){
                //递推公式
                if (nums1[i-1]==nums2[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[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Leetcode 53. 最大子数组和

题目链接: 最大子数组和
自己的思路:贪心！！！！我们只在sum大于0的时候给他继续向后加，因为如果小于等于0的话再向后加是没有意义的，只会削弱后的数！！！！

代码:

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxvalue = Integer.MIN_VALUE;
        for (int i=0;i<nums.length;i++){
            //如果sum大于0才有意义
            if (sum<=0){
                sum = nums[i];
            }else{
                sum += nums[i];
            }
            //更新最大值
            maxvalue = Math.max(sum,maxvalue);
        }
        return maxvalue;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

其他思路:动态规划！！！！！！直接动规五部曲：1、dp数组的含义：以nums[i]结尾的最大子序列的和；2、递推公式：主要分析dp[i]和哪些元素有关系，他可能在dp[i-1]的基础上加上当前元素，也可能直接放弃掉之前的累加和，直接令dp[i]=nums[i]，所以要在两者中取较大者；3、dp数组初始化：这里其实只将dp[0]初始化为nums[0]即可，但是因为后面dp[i]的递推公式有一个和nums[i]比较的，我们改成对dp[i]进行比较，所以最开始初始化的时候直接令dp=nums即可！！！！4、遍历顺序：由于后面的状态依赖前面的状态，所以我们采用从前向后遍历的方式；5、打印dp数组：主要用于debug！！！！

代码:

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = nums;
        int maxval = nums[0];
        for (int i =1;i<nums.length;i++){
            //递推公式
            dp[i] = Math.max(dp[i-1]+nums[i],dp[i]);
            maxval = Math.max(maxval,dp[i]);
        }
        return maxval;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12