300.最长递增子序列

教程视频：https://www.bilibili.com/video/BV1ng411J7xP
在这里插入图片描述

解法一：动态规划

思路：
1、dp[i]含义：表示以nums[i]结尾的最长递增子序列的长度。
2、递推公式：dp[i]=Math.max(dp[j]+1,dp[i]);
3、dp数组初始化：全部初始化为1，dp[i]=1;
4、遍历顺序：外层 i 从前向后遍历，内层 j 正序倒序都可以。
5、打印验证。

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, 1);int result = 1;//因为外层for不是从dp[0]开始遍历，考虑单个元素情况下输出1。for(int i=1;i<nums.length;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=Math.max(dp[j]+1,dp[i]);}}result=Math.max(result,dp[i]);}return result;}
}

674. 最长连续递增序列

教程视频：https://www.bilibili.com/video/BV1bD4y1778v
在这里插入图片描述

解法一：动态规划

思路：
1、dp[i]含义：表示以nums[i]结尾的最长连续递增子序列的长度。
2、递推公式：if(nums[i-1]<nums[i]) dp[i]=dp[i-1]+1;
3、dp数组初始化：全部初始化为1，dp[i]=1;
4、遍历顺序：外层 i 正序遍历，内层无需遍历。
5、打印验证。

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

解法二：双指针法

class Solution {public int findLengthOfLCIS(int[] nums) {if(nums.length==1)return 1;int maxLength=1;for(int left=0;left<nums.length;left++){int curLength=1;for(int right=left+1;right<nums.length;right++){if(nums[right-1]<nums[right]){curLength++;}else{break;}}maxLength=Math.max(maxLength,curLength);}return maxLength;}
}

718. 最长重复子数组

教程视频：https://www.bilibili.com/video/BV178411H7hV
在这里插入图片描述

解法一：动态规划

思路：
1、dp[i][j]含义：以下标 i - 1为结尾的nums1，和以下标 j - 1 为结尾的nums2，最长重复子数组长度为dp[i][j]。这里-1是为了简化初始化过程。
2、递推公式：两个数组指针始终对齐，需要同时-1if(nums2[j]==nums1[i]){ dp[i][j]=dp[i-1][j-1]+1; }
3、dp数组初始化：dp[0][j]和dp[i][0]无实际意义，为了保证递推有意义，全部初始化为0，dp[i][j]=0;
4、遍历顺序：外层遍历nums1，内层遍历nums2。正序倒序无影响。
5、打印验证。

class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];int maxLength=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;}maxLength=Math.max(maxLength,dp[i][j]);}}return maxLength;}
}//空间压缩
class Solution {public int findLength(int[] nums1, int[] nums2) {int[] dp = new int[nums2.length+1];int maxLength=0;for(int i=1;i<=nums1.length;i++){for(int j=nums2.length;j>=1;j--){if(nums1[i-1]==nums2[j-1]){dp[j]=dp[j-1]+1;}else {dp[j] = 0;//这里不能漏，否则上一阶段状态不能完全刷新}maxLength=Math.max(maxLength,dp[j]);}}return maxLength;}
}