【算法刷题day52】Leetcode：300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

本文主要是介绍【算法刷题day52】Leetcode：300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- Leetcode 300. 最长递增子序列
- - 解题思路
  - 代码
  - 总结
- Leetcode 674. 最长连续递增序列
- - 解题思路
  - 代码
  - 总结
- Leetcode 718. 最长重复子数组
- - 解题思路
  - 代码
  - 总结

草稿图网站
java的Deque

Leetcode 300. 最长递增子序列

题目：300. 最长递增子序列
解析：代码随想录解析

解题思路

dp数组的含义是以该元素为结尾的最大长度是多少，并使max来记录答案

代码

class Solution {public int lengthOfLIS(int[] nums) {int n = nums.length;int []dp = new int[n];int max = 1;Arrays.fill(dp, 1);for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i])dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(dp[i], max);}return max;}
}

总结

暂无

Leetcode 674. 最长连续递增序列

题目：674. 最长连续递增序列
解析：代码随想录解析

解题思路

和第300题的区别是，每次只要判断与前一个的对比

代码

class Solution {public int findLengthOfLCIS(int[] nums) {int n = nums.length;int []dp = new int[n];int max = 1;Arrays.fill(dp, 1);for (int i = 1; i < n; i++) {if (nums[i-1] < nums[i])dp[i] = Math.max(dp[i], dp[i-1] + 1);max = Math.max(dp[i], max);}return max;}
}

总结

暂无

Leetcode 718. 最长重复子数组

题目：718. 最长重复子数组
解析：代码随想录解析

解题思路

使用二维数组，如果nums1的第i-1个元素和第nums2的第i-2个元素如果相同，则使匹配数dp[i][j]等于dp[i-1][j-1] + 1

代码

class Solution {public int findLength(int[] nums1, int[] nums2) {int result = 0;int [][]dp = new int[nums1.length+1][nums2.length+1];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;result = Math.max(result, dp[i][j]);}}return result;}
}//滚动数组
class Solution {public int findLength(int[] nums1, int[] nums2) {int result = 0;int []dp = new int[nums2.length+1];for (int i = 1; i <= nums1.length; i++) {for (int j = nums2.length; j > 0; j--) {if (nums1[i-1] == nums2[j-1])dp[j] = dp[j-1] + 1;elsedp[j] = 0;result = Math.max(result, dp[j]);}}return result;}
}