最长连续递增子序列

Leetcode Link: 674. 最长连续递增序列 - 力扣（LeetCode）

题目

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

解法一

思路： 按照意思写即可

注意我们 res 的更新位置，思考一下为什么？

1. 每次开辟新的连续子序列前需要更新一下
2. 必需在重置 cnt 前更新
3. 最后再把最后的连续子序列更新进来。

题解：

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        cnt = 1
        res = 0
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                cnt += 1
            else:
                res = max(res, cnt)
                cnt = 1
        res = max(res, cnt)
        return res

解法二

思路：既然是easy题，我们强制自己不从暴力递归写起。

dp[i]表示第i位的最长连续递增子序列

题解：

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
        return max(dp)

解法三

这次按照从暴力递归到动态规划来做一遍

… 没想出来 …

启发和联系