AlgoPressAppearance
0674-最长连续递增序列
https://leetcode.cn/problems/longest-continuous-increasing-subsequence
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。 连续递增的子序列 可以由两个下标 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 <= 10^4
- -10^9 <= nums[i] <= 10^9
思路
动态规划，定义 dp[i] 表示截止 i 为止最长连续递增子序列的长度。 状态转移：当 nums[i] > nums[i-1] 的时候 dp[i] = dp[i-1] + 1, 否则 dp[i] = 1 重新计数 注意：返回值需要记录中间的状态值
参考代码
csharp
public class Solution {
public int FindLengthOfLCIS(int[] nums) {
int n = nums.Length;
int[] dp = new int[n];
dp[0] = 1;
int max = 1;
for(int i=1; i<n; i++){
dp[i] = nums[i] > nums[i-1] ? dp[i-1] + 1 : 1;
max = Math.Max(max,dp[i]);
}
return max;
}
}
参考代码：优化空间
因为当前状态只依赖前一个状态，所以我们可以将dp数组压缩成一个变量
csharp
public class Solution {
public int FindLengthOfLCIS(int[] nums) {
int n = nums.Length;
int curMax = 1;
int max = 1;
for(int i=1; i<n; i++){
curMax = nums[i] > nums[i-1] ? curMax + 1 : 1;
max = Math.Max(max,curMax);
}
return max;
}
}