心路历程:
这道题和递增子序列的一样,由于题目中要求连续,实际上会让状态转移更加简单,因为候选的动作集合相当于更小了。
状态:nums的区间[0, i],第i个元素和第i-1个元素的大小关系
动作:是否选择第i-1个元素
返回值:最长子序列的长度
解法:动态规划
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
@cache
def dp(i): # 以nums[i]为结尾的最长连续递增子序列
if i == 0: return 1
if nums[i] > nums[i-1]:
return dp(i-1) + 1
else:
return 1
res = 0
for k in range(len(nums)):
res = max(res, dp(k))
return res