昌邑建设网站,深圳福田网站制作公司,加强宣传阵地建设 高校 网站,品牌策划案例范文这里写目录标题 300.最长递增子序列 674. 最长连续递增序列718. 最长重复子数组 300.最长递增子序列
视频解析#xff1a; 第一层for循环遍历每一个元素#xff0c; ------- 第二层for循环找到当前元素前面有几个小于该值的元素 结尾需要统计最多的个数
class Solution {pu… 这里写目录标题 300.最长递增子序列 674. 最长连续递增序列718. 最长重复子数组 300.最长递增子序列
视频解析 第一层for循环遍历每一个元素 ------- 第二层for循环找到当前元素前面有几个小于该值的元素 结尾需要统计最多的个数
class Solution {public int lengthOfLIS(int[] nums) {int n nums.length;int[] dp new int[n];//1.初始化Arrays.fill(dp,1);int res 1;for(int i1;in;i){//第二层for(int j0;ji;j){if(nums[j]nums[i]){dp[i] Math.max(dp[i],dp[j]1);}}res Math.max(res,dp[i]);}return res;}
}674. 最长连续递增序列
方法一动态规划dp[i]表示前面有几个连续小于当前位置的值
class Solution {public int findLengthOfLCIS(int[] nums) {int n nums.length;int[] dp new int[n];Arrays.fill(dp,1);int res 1;for(int i1;in;i){if(nums[i-1]nums[i]){dp[i] dp[i-1]1;}res Math.max(res,dp[i]);}return res;}
}方法二贪心
class Solution {public int findLengthOfLCIS(int[] nums) {int n nums.length;int count 1;int res 1;for(int i0;in-1;i){if(nums[i]nums[i1]){count;}else{count1;}res Math.max(res,count);}return res;}
}718. 最长重复子数组
讲解的很好
class Solution {public int findLength(int[] A, int[] B) {int res 0;int[][] dp new int[A.length1][B.length1];for(int i1;iA.length;i){for(int j 1;jB.length;j){if(A[i-1] B[j-1]){dp[i][j] dp[i-1][j-1]1;}res Math.max(dp[i][j],res);}}return res;}
}方法二一维数组 因为当前元素依赖于x-1y-1,所以就需要从后向前去遍历 相当于在二维空间里面从最后一行开始遍历
class Solution {public int findLength(int[] A, int[] B) {int res 0;int[] dp new int[B.length1];for(int i1;iA.length;i){ // 就像是商品for(int j B.length;j0;j--){if(A[i-1]B[j-1]){dp[j] dp[j-1]1;}else{dp[j] 0;}res Math.max(res,dp[j]);}}return res;}
}
