leetcode(41)------674. 最长连续递增序列
程序员文章站
2024-02-25 09:49:52
...
674. 最长连续递增序列
Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
Example 1:
Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.
Example 2:
Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.
Note: Length of the array will not exceed 10,000.
思路分析:
从前往后两个两个比较,如果符合升序,sum 就加 1,直到不符合的时候将sum添加到K列表里,最后返回最大的数。
Python代码实现:
class Solution(object):
def findLengthOfLCIS(self, nums):
if nums ==[]:
return 0
k = [1]
sum = 1
for i in range(1,len(nums)):
if nums[i]>nums[i-1]:
sum +=1
if i+1 ==len(nums) :
return max(sum,max(k))
else:
k.append(sum)
sum = 1
return max(sum, max(k))
2.看了别人的动态规划的答案,但是提交实现不了,自己又改了改。
思路:
举个栗子:nums=[1, 2, 3, 2 , 5]
k[0] = 1, k[1] = 2, k[2] =3, k[3] =1 k[ 4 ] = 2 (这一步是通过k[i+1] = max(k [ i + 1] ,k [ j ] + 1 )来实现的,如果后一个比前一个大,后一个就加一,如果后一个不比前一个大的话,从 1 开始。对应的k是[1 , 2 , 3 ,1 , 2],最后只要返回Max(k)就可以了。
两种方法其实大同小异。
Python代码实现:
class Solution(object):
def findLengthOfLCIS(self, nums):
if nums == []:
return 0
length = len(nums)
k = [1] * length
for i in range(0, length - 1):
for j in range(i, i + 1):
if nums[i + 1] > nums[j]:
k[i + 1] = max(k[i + 1], k[j] + 1)
return max(k)