算法训练营Day44

#Java #动态规划

Feeling and experiences：

最长递增子序列：力扣题目链接

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列?是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

?

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

子序列的问题：

定义dp数组，dp数组的含义：

到达第 i 个元素时，最长的递增子序列为：dp[i]

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        int res = 1;
        Arrays.fill(dp, 1);


        for (int i = 1; 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);
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
}

? 使用两层嵌套循环遍历数组，其中外层循环控制当前元素的索引?i，内层循环遍历之前的元素，通过索引?j。

? 在内层循环中，检查?nums[i]?是否大于之前的元素?nums[j]，如果是，说明可以将当前元素加入到以?nums[j]?结尾的递增子序列中。

? 更新?dp[i]?为当前值和以?nums[j]?结尾的子序列长度加1的较大者。

? 同时，不断更新全局变量?res?为当前?dp[i]?和之前的?res?中的较大者。

这里用到的了 ： dp[j] + 1，是因为，满足条件后，要算上当前的这个数 来进行比较！

最长连续递增序列：力扣题目链接

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 

先用贪心的思想，简单又好理解：

只要第 i + 1 个元素 大于 第 i 个元素，就使得计数 + 1，否则 计数 重新置 1（从头开始）

class Solution {
    public int findLengthOfLCIS(int[] nums) {
    //先用贪心的方法来做
    //贪心思想：只要 第 i+1个元素比第 i 个元素大，就使得 计数+1，否则从头开始

    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;
    }
}

?

动态规划：

（但是感觉没有 贪心好理解） 主要用于解决一系列问题

class Solution {
    public static int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {  
                dp[i] = dp[i - 1] + 1;
            }
            res = res > dp[i] ? res : dp[i];
        }
        return res;
    }
}

?

伤心桥下春波绿，

曾是惊鸿照影来！

Fighting！

?

?