[数据结构与算法]代码随想录算法训练营day52｜300.最长递增子序列，674. 最长连续递增序列，718. 最长重复子数组

300.最长递增子序列

力扣

思路：

1. dp数组及其下标的含义：dp[i]表示i之前包括i的以nums[i]结尾的最长上升自序列的长度；

2. 递推公式：位置i的最长升序子序列长度=j从0到i-1各个位置的最长升序子序列的长度最大值+1。即，if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

3. 初始化：dp[i] = 1;

4. 遍历顺序：i在外层从前往后遍历，j在内层遍历0～i-1；

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

674. 最长连续递增序列

力扣

思路：动态规划

1. 基本同上；

2. 由于求的是最长连续序列，因此递推公式为?if(nums[i]>nums[i-1])?dp[i] = dp[i-1]+1；

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

思路：贪心算法

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length==0) return 0;
        int res = 1;
        int count = 1;
        for(int i=0;i<nums.length-1;i++){
            if(nums[i+1]>nums[i]){
                count++;
            }else{
                count = 1;
            }
            if(count>res) res = count;
        }
        return res;
    }
}

718. 最长重复子数组

力扣

思路：

1. dp数组及其下标的含义：dp[i][j]表示以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]；

2. 递推公式：if(A[i-1]==B[i-1]) dp[i][j] = dp[i-1][j-1]+1；

3. 初始化：dp[0][0]是没有意义的，但为了方便递归，初始化为0。

4. 遍历顺序：外层for循环遍历A，内层for循环遍历B（或相反）。遍历时更新最大值。

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

滚动数组

由于dp[i][j]都是由dp[i - 1][j - 1]推出的，那么就可以压缩为一维数组，也就是相当于把上一层dp[i - 1][j]拷贝到下一层dp[i][j]来继续用。

此时遍历B数组，需要从后向前，避免重复覆盖。

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