题目列表

  • 53. 最大子序和
  • 300. 最长递增子序列
  • 718. 最长重复子数组

  • 1143. 最长公共子序列

    具体代码

    53. 最大子序和

  • dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);

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

  • 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字

  • 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字

  • 每次比较 sum 和 res的大小，将最大值置为res，遍历结束返回结果

    1. class Solution {
    2.   public int maxSubArray(int[] nums) {
    3.       int res = nums[0];
    4.       int sum = nums[0];
    5.       int l = 0, r = 0;
    6.       for(int i = 1; i < nums.length; i++){
    7.           if(sum > 0) sum += nums[i];
    8.           else sum = nums[i];
    9.           res = Math.max(sum , res);
    10.       }
    11.       return res;
    12.   }
    13. }

  • 返回子数组：在上面基础上知道l和r什么时候改变就好 ```java class Solution { public int maxSubArray(int[] nums) {

    1.   int res = nums[0];
    2.   int sum = nums[0];
    3.   int l = 0, r = 0;
    4.   for(int i = 1; i < nums.length; i++){
    5.       if(sum > 0) sum += nums[i];
    6.       else {
    7.           sum = nums[i];
    8.           l = i;
    9.       }
    10.       //res = Math.max(sum , res);
    11.       if(sum > res){
    12.           res = sum;
    13.           r = i;
    14.       }
    15.   }
    16.   System.out.println(l+"  "+r);
    17.   return res;

    } }

<a name="dmDwF"></a>
#### [300. 最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
```java
class Solution {
    public int lengthOfLIS(int[] nums) {
        int res = 1;
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            res = Math.max(dp[i], res);
        }
        return res;
    }
}

718. 最长重复子数组

Image 1.png

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 0;
        //dp[i][j] == dp[i - 1][j + 1] + 1
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for(int i = 1; i < nums1.length + 1; i++){
            for(int j = 1; j < nums2.length + 1; j++){
                if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }
}

1143. 最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i < m + 1; i++){
            for(int j = 1; j < n + 1; j++){
                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[m][n];
    }
}