最长连续递增序列（ LeetCode 674 ）
一、题目描述
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 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 隔开。
提示：
- 1 <= nums.length <= 104
- -109 <= nums[i] <= 109
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长连续递增序列（ LeetCode 674 ）：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
class Solution {
public int findLengthOfLCIS(int[] nums) {
// 设置数组 dp，用来存储 nums 中以每个元素结尾的最长连续递增序列的程度
// dp[0] 表示以 nums[0] 结尾的最长连续递增序列的长度
// dp[1] 表示以 nums[1] 结尾的最长连续递增序列的长度
// dp[i] 表示以 nums[i] 结尾的最长连续递增序列的长度
int[] dp = new int[nums.length];
// 首先将数组 dp 里面的值都初始化为 1
// 1 表示以当前元素结尾的最长连续递增序列的长度为 1
// 即最长连续递增序列就是当前元素本身
Arrays.fill(dp, 1);
// 设置一个变量用来存储最长连续递增序列的结果
int maxLength = 1;
// 从 1 开始，直到 dp.length ，往 dp 里面填充结果
for(int i = 1 ; i < dp.length ; i++){
// 索引 0 1 2 3 4 5 6
// nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
// 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
// 此时发现 i - 1 对应的数字为 2
// nums[i ] > nums[ i - 1 ]，意味着最长连续递增序列的长度增加了
// 需要更新 dp[i]
if(nums[i] > nums[ i - 1 ]){
// 4、更新 dp[i]
dp[i] = dp[ i - 1] + 1;
}
// 在更新 dp[i] 的过程中，发现了一个更长的子序列
if(maxLength < dp[i]){
// 那么把更长的子序列的长度赋值给 maxLength
maxLength = dp[i];
}
}
// 最后返回 maxLength 就行
return maxLength;
}
}
2、C++ 代码
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
// 设置数组 dp，用来存储 nums 中以每个元素结尾的最长连续递增序列的程度
// dp[0] 表示以 nums[0] 结尾的最长连续递增序列的长度
// dp[1] 表示以 nums[1] 结尾的最长连续递增序列的长度
// dp[i] 表示以 nums[i] 结尾的最长连续递增序列的长度
// 首先将数组 dp 里面的值都初始化为 1
// 1 表示以当前元素结尾的最长连续递增序列的长度为 1
// 即最长连续递增序列就是当前元素本身
vector<int> dp( nums.size() , 1 );
// 设置一个变量用来存储最长连续递增序列的结果
int maxLength = 1;
// 从 1 开始，直到 dp.length ，往 dp 里面填充结果
for(int i = 1 ; i < dp.size() ; i++){
// 索引 0 1 2 3 4 5 6
// nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
// 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
// 此时发现 i - 1 对应的数字为 2
// nums[i ] > nums[ i - 1 ]，意味着最长连续递增序列的长度增加了
// 需要更新 dp[i]
if(nums[i] > nums[ i - 1 ]){
// 4、更新 dp[i]
dp[i] = dp[ i - 1] + 1;
}
// 在更新 dp[i] 的过程中，发现了一个更长的子序列
if(maxLength < dp[i]){
// 那么把更长的子序列的长度赋值给 maxLength
maxLength = dp[i];
}
}
// 最后返回 maxLength 就行
return maxLength;
}
};
3、Python 代码
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
# 设置数组 dp，用来存储 nums 中以每个元素结尾的最长连续递增序列的程度
# dp[0] 表示以 nums[0] 结尾的最长连续递增序列的长度
# dp[1] 表示以 nums[1] 结尾的最长连续递增序列的长度
# dp[i] 表示以 nums[i] 结尾的最长连续递增序列的长度
# 首先将数组 dp 里面的值都初始化为 1
# 1 表示以当前元素结尾的最长连续递增序列的长度为 1
# 即最长连续递增序列就是当前元素本身
dp = [ 1 for _ in range(len(nums))]
# 设置一个变量用来存储最长连续递增序列的结果
maxLength = 1
# 从 1 开始，直到 dp.length ，往 dp 里面填充结果
for i in range( 1 ,len(dp)):
# 索引 0 1 2 3 4 5 6
# nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
# 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
# 此时发现 i - 1 对应的数字为 2
# nums[i ] > nums[ i - 1 ]，意味着最长连续递增序列的长度增加了
# 需要更新 dp[i]
if nums[i] > nums[ i - 1 ]:
# 4、更新 dp[i]
dp[i] = dp[ i - 1] + 1
# 在更新 dp[i] 的过程中，发现了一个更长的子序列
if maxLength < dp[i]:
# 那么把更长的子序列的长度赋值给 maxLength
maxLength = dp[i]
# 最后返回 maxLength 就行
return maxLength
