建网站 需要签署协议,建局域网网站,简约式网站模板,建立传媒公司网站代码随想录训练营二刷第五十四天 | 300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组
一、300.最长递增子序列
题目链接#xff1a;https://leetcode.cn/problems/longest-increasing-subsequence/ 思路#xff1a;定义dp[i]表示从0到i的闭区间的最长子序列长…代码随想录训练营二刷第五十四天 | 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.length1][nums2.length1];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;}
}
