欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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)

673. 最长递增子序列的个数