代码随想录算法训练营第四十一天-300最长递增子序列、674最长连续递增序列、718最长重复子数组

前言
状态：300 看解析，674AC，718看解析
更新

1	24-07-01 初始记录

初步题解

300 最长递增子序列

题目链接：(https://leetcode.cn/problems/longest-increasing-subsequence)

确定 dp[i] 的含义：dp[i] 表示第 i 个下标前的最长递增子序列的长度
递推公式：dp[i] = Math.max(dp[i], dp[j] + 1)。
dp 数组的初始化：dp 数组所有元素的初始化值都为 1。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

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

674 最长连续递增序列

题目链接：(https://leetcode.cn/problems/longest-continuous-increasing-subsequence)

确定 dp[i] 的含义：dp[i] 表示第 i 个下标前的最长连续递增子序列的长度
递推公式：dp[i] = Math.max(dp[i], dp[i - 1] + 1)。
dp 数组的初始化：dp 数组所有元素的初始化值都为 1。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）

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

718 最长重复子数组

确定 dp[i][j] 的含义：num1 到 i - 1；num2 到 j - 1 位置的最长重复数组。
递推公式：dp[i][j] = dp[i - 1][j - 1] + 1; 。
dp 数组的初始化：dp 数组所有元素的初始化值都为 0。
遍历顺序：从前向后遍历。
打印 dp 数组（用于 debug）题目链接：(https://leetcode.cn/problems/maximum-length-of-repeated-subarray)

public int findLength(int[] nums1, int[] nums2) {  
    int[][] dp = new int[nums1.length + 1][nums2.length + 1];  
  
    int maxLength = 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;  
            }  
            maxLength = Math.max(dp[i][j], maxLength);  
        }  
    }  
  
    return maxLength;  
}

看解析