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

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

一、300.最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/
思路：定义dp[i]表示从0到i的闭区间的最长子序列长度。求任一个dp[i]都要用每一个数与该数比较。
dp[me] = max(dp[me], dp[j] + 1);

class Solution {public int lengthOfLIS(int[] nums) {if(nums.length == 1) return 1;int[] dp = new int[nums.length];Arrays.fill(dp, 1);int max = 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);}}max = Math.max(max, dp[i]);}return max;}
}

二、674. 最长连续递增序列

题目链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
思路：连续数组单层循环即可，只要不连续就又从1开始，连续就累加。

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

三、718. 最长重复子数组

题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
思路：依旧是从区间出发，定义dp[i][j]表示[0,i][0,j]区间中最长连续相等的子数组的长度。

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