代码随想录算法训练营第五二天 | 递增子序列、最长重复子数组

本文主要是介绍代码随想录算法训练营第五二天 | 递增子序列、最长重复子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最长递增子序列

class Solution {// dp[i] i 之前 包括 i 的 以 nums[i] 结尾的最长递增子序列长度// 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。// if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);  // 取dp[j] + 1的最大值// 每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.public int lengthOfLIS(int[] nums) {if (nums.length == 1) return 1;int[] dp = new int[nums.length];Arrays.fill(dp, 1);int res = 0;  // 写 1 也可以， 因为上面对nums.length == 1进行了判断，所以不用担心会是0的问题for (int i = 1; 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);}res = Math.max(res, dp[i]);}}return res;}
}

最长连续递增序列

class Solution {// dp[i] : 最长连续递增子序列// 如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。// dp[i] = dp[i - 1] + 1;// 因为本题要求连续递增子序列，所以就只要比较nums[i]与nums[i - 1]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, 1);int res = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;} res = Math.max(res, dp[i]);}return res;}
}

不连续递增子序列的跟前 0-i 个状态有关，连续递增的子序列只跟前一个状态有关

最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。

class Solution {// dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。// dp[i][j] = dp[i - 1][j - 1] + 1; 遍历i 和 j 要从1开始！// dp[i][0] 和dp[0][j]初始化为0。public int findLength(int[] nums1, int[] nums2) {int result = 0;int[][] dp = new int[nums1.length + 1][nums2.length + 1];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(result, dp[i][j]);}}}return result;}
}

class Solution {public int findLength(int[] nums1, int[] nums2) {int result = 0;int[] dp = new int[nums2.length + 1];for (int i = 1; i <= nums1.length; i++) {for (int j = nums2.length; j > 0; 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;}
}