网站怎样免费推广,网站建设 银川,网站建设亿码酷专注,联想公司网站建设现状给定一个未经排序的整数数组#xff0c;找到最长且 连续递增的子序列#xff0c;并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r#xff08;l r#xff09;确定#xff0c;如果对于每个 l i r#xff0c;都有 nums[i] nums[i 1] 找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 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。提示
1 nums.length 104-109 nums[i] 109
class Solution {
public:int findLengthOfLCIS(vectorint nums) {//普通int res 1,count 1;for(int i 1;i nums.size();i){if(nums[i] nums[i-1]){count;}else count 0;res max(res,count);}return res;}
};dp
class Solution {
public:int findLengthOfLCIS(vectorint nums) {//dp//最长连续的。//dp[i]:以nums[i]为结尾的序列最长为dp[i];//递推关系如果nums[i-1] nums[i] 那么就可以把nums[i]加入以nums[i-1]为结尾的序列中。 即 dp[i] max(dp[i], dp[i-1] 1);//初始化 1int res 1;vectorintdp(nums.size()1,1);for(int i 1;i nums.size();i){if(nums[i] nums[i-1]){dp[i] max(dp[i], dp[i-1] 1);}res max(res,dp[i]);}return res;}
};
