代码随想录训练营day52 最长递增子序列 最长连续递增序列 最长重复子数组

最长递增子序列

dp[i]的定义, 表示i之前包括i的以nums[i]结尾最长上升子序列的长度递推: if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)初始化: 每个i对应的dp[i]起始大小都为1 (通过arrays.fill)这里两个循环, 来比较, 所以起始点不同然后最后更新获得result长度

class Solution {public int lengthOfLIS(int[] nums) {int res = 0;int[] dp = new int[nums.length];//初始化数组全部为1Arrays.fill(dp, 1);//两个循环一前一后遍历数组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);}}//最后定义下resif(dp[i] > res){res = dp[i];}}return res;}}

最长连续递增序列

区别就在于连续

动态规划

数组定义: 以下标i为结尾的数组的连续递增的子序列长度为dp[i]递推: 这里是连续, 所以比较i+1和i, 如果满足, dp[i+1] = dp[i] + 1(就是长度加一)dp[i]初始化为1

(len是为了记录最大值, 如果dp[i+1]大于他, 就更新)

class Solution {public int findLengthOfLCIS(int[] nums) {int len = 1;int[] dp = new int[nums.length];Arrays.fill(dp, 1); //由于是+1, 所以最后还得-1for(int i = 0; i < nums.length - 1; i++){if(nums[i+1] > nums[i]){//dp[i]初始化的定义是长度噢dp[i + 1] = dp[i] + 1;}if(dp[i + 1] > len){len = dp[i + 1];}}return len;}}

贪心: 如果连续递增了, count++, 否则count=1, 从头开始

class Solution {public int findLengthOfLCIS(int[] nums) {int count = 1;int res = 1;for(int i = 0; i < nums.length - 1; i++){if(nums[i + 1] > nums[i]){count++;} else {count = 1;}if(count > res){res = count;}}return res;}}

最长重复子数组

dp[i][j]: 以下标i-1为结尾的A和以下标j-1为结尾的B, dp[][]是最长重复子数组长度

(这里用i-1,j-1更加方便)

递推: 当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1dp[0][j]和dp[i][0]都需要初始化为0, 才能保证A[0]B[0]相等时, dp[0][0]+1为1这里遍历内外顺序都可以

class Solution {public int findLength(int[] nums1, int[] nums2) {int res = 0;int[][] dp = new int[nums1.length + 1][nums2.length + 1];//初始化因为是0, 所以没有真正意义上的innifor(int i = 1; i < nums1.length + 1; i++){for(int j = 1; j < nums2.length + 1; j++){//如果两个数组的ij相同, 那么可以递推//注意一开始的定义是要-1if(nums1[i - 1] == nums2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;}//还是要更新if(dp[i][j] > res){res=dp[i][j];} }}return res;}}

一维数组方法: 此时遍历数组2时, 要从后往前遍历, 防止重复覆盖

class Solution {public int findLength(int[] nums1, int[] nums2) {int res = 0;int[] dp = new int[nums2.length + 1];//初始化因为是0, 所以没有真正意义上的innifor(int i = 1; i <= nums1.length; i++){for(int j = nums2.length; j > 0; j--){//如果两个数组的ij相同, 那么可以递推//注意一开始的定义是要-1if(nums1[i - 1] == nums2[j - 1]){dp[j] = dp[j - 1] + 1;} else {dp[j] = 0;}//还是要更新if(dp[j] > res){res=dp[j];} }}return res;}