网站软文制作,天津谁做网站,如何制作个人网页设计,唐山网站制作服务公司674. 最长连续递增序列 - 力扣#xff08;LeetCode#xff09;
给定一个未经排序的整数数组#xff0c;找到最长且 连续递增的子序列#xff0c;并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r#xff08;l r#xff09;确定#xff0c;如果对于每…674. 最长连续递增序列 - 力扣LeetCode
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl 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。 思路和分析
本题相对于leetCode 300.最长递增子序列 最大区别在于 “连续”
不连续递增子序列的跟前0-i 个状态有关两个for循环连续递增的子序列只跟前一个状态有关一个for循环
方法一动态规划
1.确定dp数组dp table以及下标的含义
dp[i]以下标i为结尾的连续递增的子序列长度为dp[i]
注意这里的定义一定是以下标i为结尾并不是说一定以下标0为起始位置。
2.确定递推公式
如果 nums[i] nums[i - 1]那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 1
即dp[i] dp[i - 1] 1;
3.dp数组初始化
以下标i为结尾的连续递增的子序列长度最少也应该是1即就是nums[i]这一个元素。所以dp[i]应该初始1;
4.确定遍历顺序
从递推公式上可以看出 dp[i 1]依赖dp[i]所以一定是从前向后遍历
for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) { // 连续记录dp[i] dp[i - 1] 1;}
}
5.举例推导dp数组 class Solution {
public:int findLengthOfLCIS(vectorint nums) {if (nums.size() 0) return 0;int result 1;vectorint dp(nums.size() ,1);for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) { // 连续记录dp[i] dp[i - 1] 1;}if (dp[i] result) result dp[i];}return result;}
};
时间复杂度O(n)空间复杂度O(n)
方法二贪心策略
当遇到nums[i] nums[i - 1]的情况count否则count 为 1,记录下count的最大值即可 class Solution {
public:int findLengthOfLCIS(vectorint nums) {if (nums.size() 0) return 0;int count1;int result1;// 连续子序列最少也是1for(int i1;inums.size();i) {// 连续记录if(nums[i]nums[i-1]) count count 1;// 不连续count从头开始else count1;result max(count,result);}return result;}
};时间复杂度O(n)空间复杂度O(1)
来自代码随想录课堂截图 参考和推荐文章、视频
代码随想录 (programmercarl.com)
动态规划之子序列问题重点在于连续| LeetCode674.最长连续递增序列_哔哩哔哩_bilibili
