代码随想录训练营第53天|1143.最长公共子序列，1025.不相交的线，53.最大子数组和

1143.最长公共子序列

文章

代码随想录|1143.最长公共子序列

思路

与昨天的连续情况不同，今天要在访问元素不同时维持$dp[i][j]=Max(dp[i][j-1],dp[i-1][j])$

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int i, j, m, n;
        m = text1.length();
        n = text2.length();
        int[][] dp = new int[m][n];
        for (i = 0; i < m; ++i) {
            for (j = 0; j < n; ++j) {
                if (i > 0 && j > 0 && text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else if (i == 0 && j > 0) {
                    dp[i][j] = text1.charAt(i) == text2.charAt(j) ? 1 : dp[i][j - 1];
                } else if (i > 0 && j == 0) {
                    dp[i][j] = text1.charAt(i) == text2.charAt(j) ? 1 : dp[i - 1][j];
                } else if (i > 0 && j > 0){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                } else {
                    dp[i][j] = text1.charAt(i) == text2.charAt(j) ? 1 : 0;
                }
                // System.out.print(" " + dp[i][j]);
            }
            // System.out.println();
        }
        return dp[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

1035.不相交的线

文章

代码随想录|1035.不相交的线

思路

与1143完全一样，表过不提

代码

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int i, j, m, n;
        m = nums1.length;
        n = nums2.length;
        int[][] dp = new int[m][n];
        for (i = 0; i < m; ++i) {
            for (j = 0; j < n; ++j) {
                if (i > 0 && j > 0) {
                    if (nums1[i] == nums2[j]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                    }
                } else if (i == 0 && j == 0){
                    dp[i][j] = nums1[i] == nums2[j] ? 1 : 0;
                } else if (i > 0) {
                    dp[i][j] = nums1[i] == nums2[j] ? 1 : dp[i - 1][j];
                } else {
                    dp[i][j] = nums1[i] == nums2[j] ? 1 : dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

53.最大子数组和

文章

代码随想录|0053.最大子序和（动态规划）

思路

$$dp[i]=Max(dp[i],nums[i]+dp[i-1])$$
dp过程中维护最大值，最后返回最大值

代码

class Solution {
   public int maxSubArray(int[] nums) {
       int ans = nums[0];
       int i, n;
       n = nums.length;
       int[] dp = new int[n];
       dp[0] = nums[0];
       for (i = 1; i < n; ++i) {
           dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];
           ans = ans > dp[i] ? ans : dp[i];
       }
       return ans;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结

思路能一下看到七八分，但是从dp[i][j-1]和dp[i-1][j]中找最大值并没有第一时间想到