代码随想录算法训练营 Day 52 | 300.最长递增子序列,674.最长连续递增序列,718.最长重复子数组

300.最长递增子序列

讲解链接：代码随想录-300.最长递增子序列

1. dp[i]的定义：

   1. dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2. 状态转移方程

   1. 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

      所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

      注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

3. dp[i]的初始化

   1. 每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.

4. 确定遍历顺序

   1. dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。

      j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。

      遍历i的循环在外层，遍历j则在内层，代码如下：

      for (int i = 1; i < nums.size(); i++) {
          for (int j = 0; j < i; j++) {
              if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
          }
          if (dp[i] > result) result = dp[i]; // 取长的子序列
      }
      

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        result = Math.max(result, dp[i]);
    }
    return result;
}

674.最长连续递增序列

讲解链接：代码随想录-674.最长连续递增序列

public int findLengthOfLCIS(int[] nums) {
    if (nums.length < 2) return 1;
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int result = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i - 1] < nums[i]) {
            dp[i] = dp[i - 1] + 1;
        }
        result = Math.max(dp[i], result);
    }
 
    return result;
}

718.最长重复子数组

讲解链接：代码随想录-718.最长重复子数组

二维数组

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

滚动数组

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