网站建设课程小结,网站开发学什么语言好,wordpress网站访问验证码,海口网球给定一个未经排序的整数数组#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 10^4
-109 nums[i] 10^9 解题思路【动态规划】 dp[i]表示num[i]结尾的连续递增子序列长度dp[i] dp[i - 1] 1当 nums[i]nums[i - 1] 时 此情况下连续递增子序列长度为 dp[i - 1]1 当 nums[i]nums[i - 1] 时此情况上升子序列不成立跳过。初始化dp[i] 1 题目差异参考博文[leetcode]300_最长递增子序列-CSDN博客 class Solution:def longest_continous_substring_dp(self, nums):length len(nums)dp [1] * lengthfor i in range(1, length):if nums[i] nums[i - 1]:dp[i] dp[i - 1] 1return max(dp)
if __name__ __main__:num eval(input())solution Solution()print(solution.longest_continous_substring_dp(num)) 其他思路【贪心】 局部最优num[i] nums[i - 1]连续序列长度 count 1其他情况 count 1 全局最优最大的连续长度count def longest_continous_substring_greedy(self, nums):length len(nums)res 1count 1for i in range(1, length):if nums[i] nums[i - 1]:count 1else:count 1res max(res, count)return res 仅作为代码记录方便自学自查自纠
