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

300.最长递增子序列

题目链接：300.最长递增子序列
文档讲解：代码随想录
状态：不会，递推状态的时候只想着如何从dp[i-1]推导dp[i]，没想过可能需要枚举dp[0-i]

思路：
找出所有比自己小的数字的dp[j],在这些dp[j]中找到最大的,然后加1。
也就是 j 从[0,i) 中 if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

题解：

public int lengthOfLIS(int[] nums) {
    // 如果数组长度为1，最长递增子序列即为数组的第一个元素
    if (nums.length == 1) {
        return nums[0];
    }

    // 创建dp数组，dp[i]表示以nums[i]结尾的最长递增子序列的长度
    int[] dp = new int[nums.length];
    // 初始化dp数组，每个位置的初始值为1，因为每个元素本身就是一个递增子序列
    Arrays.fill(dp, 1);

    // 记录最长递增子序列的长度
    int max = 0;

    // 从第1个元素开始遍历
    for (int i = 1; i < nums.length; i++) {
        // 在第i个元素之前的元素中寻找
        for (int j = 0; j < i; j++) {
            // 如果找到一个比nums[i]小的元素nums[j]
            if (nums[j] < nums[i]) {
                // 更新dp[i]，表示以nums[i]结尾的最长递增子序列的长度
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
        }
        // 更新全局最大值
        max = Math.max(max, dp[i]);
    }

    // 返回最长递增子序列的长度
    return max;
}

674. 最长连续递增序列

题目链接：674. 最长连续递增序列
文档讲解：代码随想录
状态：终于有个简单题了。。。

思路：

因为连续，所以不需要向上题一样比较nums[j]与nums[i]了，只要比较nums[i] 和 nums[i - 1]，如果是大于则dp[i] = dp[i - 1] + 1;

题解：

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

718. 最长重复子数组

题目链接：718. 最长重复子数组
文档讲解：代码随想录
状态：不会

思路：
dp[i][j] 表示以 nums1[i-1] 结尾的子数组A和以 nums2[j-1] 结尾的子数组B之间的最长重复子数组的长度。
为了得到 dp[i][j]，必须在 dp[i-1][j-1] 的基础上加1，否则就不是重复子数组。
因此，当 nums1[i-1] 等于 nums2[j-1] 时，dp[i][j] = dp[i-1][j-1] + 1。

题解：

	public int findLength(int[] nums1, int[] nums2) {
        // 创建二维数组 dp，大小为 (nums1.length + 1) x (nums2.length + 1)
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int res = 0; // 存储最大公共子数组的长度

        // 遍历 nums1 和 nums2 的每一个元素
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                // 如果 nums1[i-1] 和 nums2[j-1] 相等
                if (nums1[i - 1] == nums2[j - 1]) {
                    // 则 dp[i][j] 等于 dp[i-1][j-1] + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                // 更新最大公共子数组的长度
                res = Math.max(res, dp[i][j]);
            }
        }
        return res; // 返回最大公共子数组的长度
    }


    public int findLength2(int[] nums1, int[] nums2) {
        // 创建一维数组 dp，大小为 nums2.length + 1
        int[] dp = new int[nums2.length + 1];
        int result = 0; // 存储最大公共子数组的长度

        // 遍历 nums1 的每一个元素
        for (int i = 1; i <= nums1.length; i++) {
            // 从后往前遍历 nums2 的每一个元素
            for (int j = nums2.length; j > 0; j--) {
                // 如果 nums1[i-1] 和 nums2[j-1] 相等
                if (nums1[i - 1] == nums2[j - 1]) {
                    // 则 dp[j] 等于 dp[j-1] + 1
                    dp[j] = dp[j - 1] + 1;
                } else {
                    // 否则 dp[j] 重置为 0
                    dp[j] = 0;
                }
                // 更新最大公共子数组的长度
                result = Math.max(result, dp[j]);
            }
        }
        return result; // 返回最大公共子数组的长度
    }