算法训练营Day52(子序列系列)

300.最长递增子序列??

300. 最长递增子序列 - 力扣（LeetCode）

dp数组:

? ? ? ? i之前包括i，到nums[i]的最长递增子序列的长度

递推公式：

? ? ? ? 例子模拟? 5? 3? 7 8? 3<5? 不操作，? 7>5,.+1

? ? ? ? 如nums[i]>nums[j]? ?dp[i] = dp[j] +1;

主要理解这两个还有双层for循环，这道题用递归五部曲不那么适用，先看双层for循环的逻辑顺序最好，然后看代码脑海里模拟以下

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

                }
            }
        }
        int res =Integer.MIN_VALUE;
        for(int i = 0;i<dp.length;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

674.?最长连续递增序列?

674. 最长连续递增序列 - 力扣（LeetCode）

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        //以i为结尾的最长连续递增子序列为dp[i]
        int [] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for(int i = 1;i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                dp[i] = dp[i-1]+1;
            }
        }
        int res = Integer.MIN_VALUE;
        for(int num:dp){
            res = Math.max(res,num);
        }
        return res;
    }
}

718.?最长重复子数组??

718. 最长重复子数组 - 力扣（LeetCode）

?

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        //表示i-1  j-1结尾的nums的最长重复子数组
        //这样写可以防止dp[0][j]和dp[i][0]的复杂的初始化
        int [][] dp = new int[len1+1][len2+1];
        //初始化，第一行第一列没意义，递推公式是+1 状态初始为0
        
        int res = Integer.MIN_VALUE;
        for(int i = 1;i<=len1;i++){
            for(int j = 1;j<=len2;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;

    }
}