代码随想录算法训练营day52 | 300.最长递增子序列，674. 最长连续递增序列，718. 最长重复子数组

代码随想录算法训练营day52 | 300.最长递增子序列，674. 最长连续递增序列，718. 最长重复子数组

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、打印验证。

classSolution{publicintlengthOfLIS(int[] nums){int[] dp =newint[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、打印验证。

classSolution{publicintfindLengthOfLCIS(int[] nums){int[] dp =newint[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;}}

解法二：双指针法

classSolution{publicintfindLengthOfLCIS(int[] nums){if(nums.length==1)return1;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、递推公式：两个数组指针始终对齐，需要同时-1

if(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、打印验证。

classSolution{publicintfindLength(int[] nums1,int[] nums2){int[][] dp =newint[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;}}//空间压缩classSolution{publicintfindLength(int[] nums1,int[] nums2){int[] dp =newint[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;}}

总结

1、子数组相关题目要从尾部元素去定义dp数组；
2、两个不同序列比较时，递推公式需要考虑指针对齐的问题；
3、718. 最长重复子数组中dp[i][j]表示索引为i-1和j-1处的最长公共子序列，可以简化初始化状态。