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

300.最长递增子序列 

题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];dp[0] = 1;for(int i = 1;i<nums.length;i++){int temp = i;int max = 1;while(--temp>=0){if(nums[temp]<nums[i])max = Math.max(max,dp[temp]+1);}dp[i] = max;}int res = 0;for(int i = 0;i<nums.length;i++){res = Math.max(res,dp[i]);}return res;}
}

674. 最长连续递增序列 

题目：给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];dp[0] = 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;}}int res = 1;for(int i = 0;i<nums.length;i++){res = Math.max(res,dp[i]);}return res;}
}

718. 最长重复子数组  

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

方法一：暴力解法

class Solution {public int findLength(int[] nums1, int[] nums2) {int res = 0;for(int i = 0;i<nums1.length;i++){for(int j =0;j<nums2.length;j++){int index1 = i;int index2 = j;while(index1<nums1.length&& index2<nums2.length && nums1[index1]==nums2[index2]){index1++;index2++;}res = Math.max(res,index1-i);}}return res;}
}

方法二：动态规划

class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length][nums2.length];int res = 0;for (int i = 0; i < nums1.length; i++) {if (nums1[i] == nums2[0]) {dp[i][0] = 1;res = 1;}}for (int j = 0; j < nums2.length; j++) {if (nums2[j] == nums1[0]) {dp[0][j] = 1;res = 1;}}for (int i = 1; i < nums1.length; i++) {for (int j = 1; j < nums2.length; j++) {if (nums1[i] == nums2[j])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = 0;res = Math.max(res, dp[i][j]);}}return res;}
}