C国演义 [第六章]

最长递增子序列

力扣链接

给你一个整数数组 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 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1

  • 提示:
    1 <= nums.length <= 2500
    -104 <= nums[i] <= 104

题目理解

最长递增子序列是动态规划的经典题型
子序列 — — 由原数组派生而来, 删除(或不删除)数组中的元素而不改变数组的原有顺序

步骤

dp含义

dp[i] — — 以nums[i]结尾的最长递增子序列的最大长度

🗨️为什么是以nums[i]结尾??

  • 我们在做递增比较时, 一定会比较 nums[i] 和 nums[j] ( j的区间是 [0, i - 1] ),
    那么两个递增子序列一定是以 nums[i] 和 nums[j] 结尾的
    如果不是比较结尾元素, 那么递增就没有意义啦

递推公式

递增比较区间是 [0, i - 1]
递增比较条件是 num[i] > nums[j] (j 的区间是 [0, i - 1])
由于是一个区间, 那么就要在区间里面取一个最大值

if(nums[i] > num[j])
	dp[i] = max(dp[i], dp[j] + 1);

举个例子:
nums = [1, 3, 7, 5, 9, 6 ], nums[i] = 9:
j 遍历到 1, 9 > 1, dp[4] = max(dp[4], dp[0] + 1) = max(1, 2) = 2
j 遍历到 3, 9 > 3, dp[4] = max(dp[4], dp[1] + 1) = max(2, 3) = 3
j 遍历到 7, 9 > 7, dp[4] = max(dp[4], dp[2] + 1) = max(3, 4) = 4
j 遍历到 5, 9 > 5, dp[4] = max(dp[4], dp[3] + 1) = max(4, 4) = 4

初始化

🗨️由递推公式得知: 都是从dp[0] 推导上去的, dp[0] 该怎样初始化呢?

  • 回顾一下dp的含义 — — 以nums[i]结尾的最长递增子序列的长度
    那么dp[0] — — 以nums[0]结尾的最长递增子序列的长度 — — 那么dp[0] = 1

🗨️那么其他的应该怎样初始化?

  • 每一个数, 都是一个递增子序列 — — 其他的也应该初始化为 1

dp数组都初始化为1

遍历顺序

由递推公式得知: 是由前到后的顺序
那么遍历顺序就是, 从小到大

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        // 初始化
        // dp[i] -- -- 以dp[i]结尾的最长递增子序列的最大长度
        vector<int> dp(nums.size(), 1);
        
        int result = 1;  // 记录最长递增子序列的最大长度
                        // 初始化为 1 -- -- 也是为了避免讨论一个数的情况
        for(int i = 1; i < nums.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            
            result = max(result, dp[i]);
        }
        
        return result;
    }
};

最终的结果并不是 dp[nums.size() - 1],
而是需要遍历dp[i], 然后找到一个最大值

举个例子:
nums = [1, 3, 5, 7, 6 ], 我们发现: 最长递增子序列是 1, 3, 5, 7
是以 7结尾的, 而不是以 6结尾的

最长连续递增序列

力扣链接

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 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 隔开。
示例 2:
输入:nums = [2,2,2,2,2]
输出:1
解释:最长连续递增序列是 [2], 长度为1。

  • 提示:
    1 <= nums.length <= 104
    -109 <= nums[i] <= 109

题目理解

这个题目跟上个题目的思路是一样的, 但是有个区别就是 连续 && 递增
上个题目只要求 递增即可
那么这个时候, 就简单很多:
递增子序列 — — 需要在 [0, i - 1] 中比较, 找出最大值
连续递增子序列 ---- — 仅仅只需要 dp[i - 1]的情况

步骤

dp含义

dp[i] — — 以nums[i]结尾的最长连续递增子序列的长度

递推公式

连续 — — nums[i] > nums[i - 1]
那么递推公式就如下:

if(nums[i] > nums[i - 1]) 
	dp[i] = dp[i - 1] + 1;

初始化

🗨️由递推公式得知: 都是从dp[0] 推导上去的, dp[0] 该怎样初始化呢?

  • 回顾一下dp的含义 — — 以nums[i]结尾的最长递增子序列的长度
    那么dp[0] — — 以nums[0]结尾的最长递增子序列的长度 — — 那么dp[0] = 1

🗨️那么其他的应该怎样初始化?

  • 每一个数, 都是一个递增子序列 — — 其他的也应该初始化为 1

dp数组都初始化为1

遍历顺序

由递推公式得知: 是从前到后的遍历顺序
那么就是 从小到大的遍历顺序

代码

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) 
    {
        vector<int> dp(nums.size(), 1);
        
        int result = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] > nums[i - 1])
                dp[i] = dp[i - 1] + 1;
            
            result = max(result, dp[i]);
        }
        
        return result;
    }
};


饭能够一日不吃,觉能够一日不睡,书不能够一日不读 — — 毛泽东

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>