代码随想录训练营day52, 最长递增子序列, 最长连续递增序列, 最长重复子数组

最长递增子序列

1. dp[i]的定义, 表示i之前包括i的以nums[i]结尾最长上升子序列的长度
2. 递推: if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
3. 初始化: 每个i对应的dp[i]起始大小都为1 (通过arrays.fill)
4. 这里两个循环, 来比较, 所以起始点不同
5. 然后最后更新获得result长度

class Solution {
    public int lengthOfLIS(int[] nums) {
        int res = 0;
        int[] dp = new int[nums.length];
				//初始化数组全部为1
        Arrays.fill(dp, 1);
        //两个循环一前一后遍历数组
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            //最后定义下res
            if(dp[i] > res){
                res = dp[i];
            }
        }
        return res;
    }
}

最长连续递增序列

区别就在于连续

动态规划

1. 数组定义: 以下标i为结尾的数组的连续递增的子序列长度为dp[i]
2. 递推: 这里是连续, 所以比较i+1和i, 如果满足, dp[i+1] = dp[i] + 1(就是长度加一)
3. dp[i]初始化为1

(len是为了记录最大值, 如果dp[i+1]大于他, 就更新)

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int len = 1;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1); 
        //由于是+1, 所以最后还得-1
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i+1] > nums[i]){
                //dp[i]初始化的定义是长度噢
                dp[i + 1] = dp[i] + 1;
            }
            if(dp[i + 1] > len){
                len = dp[i + 1];
            }
        }
        return len;
    }
}

贪心: 如果连续递增了, count++, 否则count=1, 从头开始

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int count = 1;
        int res = 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;
    }
}

最长重复子数组

1. dp[i][j]: 以下标i-1为结尾的A和以下标j-1为结尾的B, dp[][]是最长重复子数组长度

(这里用i-1,j-1更加方便)

1. 递推: 当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1
2. dp[0][j]和dp[i][0]都需要初始化为0, 才能保证A[0]B[0]相等时, dp[0][0]+1为1
3. 这里遍历内外顺序都可以

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        //初始化因为是0, 所以没有真正意义上的inni
        for(int i = 1; i < nums1.length + 1; i++){
            for(int j = 1; j < nums2.length + 1; j++){
                //如果两个数组的ij相同, 那么可以递推
                //注意一开始的定义是要-1
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                //还是要更新
                if(dp[i][j] > res){
                    res=dp[i][j];
                }   
            }
        }
        return res;
    }
}

一维数组方法: 此时遍历数组2时, 要从后往前遍历, 防止重复覆盖

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int res = 0;
        int[] dp = new int[nums2.length + 1];
        //初始化因为是0, 所以没有真正意义上的inni
        for(int i = 1; i <= nums1.length; i++){
            for(int j = nums2.length; j > 0; j--){
                //如果两个数组的ij相同, 那么可以递推
                //注意一开始的定义是要-1
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[j] = dp[j - 1] + 1;
                } else {
                    dp[j] = 0;
                }
                //还是要更新
                if(dp[j] > res){
                    res=dp[j];
                }   
            }
        }
        return res;
    }