使用 python 的递归方法中的最长递增子数组

Question

我试过不用递归方法解决这个问题

def findLongest():
    nums=[1, 9, 3, 10, 4, 20, 2]
    f = c = lastMax = p1 = 0

    while (p1 < len(nums) - 1):
        p2 = p1 + 1
        while (p2 < len(nums) - 1):
            if nums[p2] > nums[p1]:
                c += 1
                if f == 0:
                    f = 1
                    p1 = p2
            p2 += 1

        if c > lastMax:
            lastMax = c
            f = 0
            c = 0
        p1 += 1
    return lastMax

我在网上搜索了很多，找到了一个很好理解的简单递归方法。

Answer 1

这将找到列表中最长的单调递增子序列的长度。这不是适合递归解决方案的问题。

def findLongest(nums):
    last = 99999999
    maxSeq = 0
    for n in nums:
        if n > last:
            seq += 1
            if seq > maxSeq:
                maxSeq = seq
        else:
            seq = 1
        last = n
    return maxSeq
print( findLongest([1, 9, 3, 10, 4, 20, 2]))

这是一个递归版本。

def find1(last, nums, n):
    if nums and nums[0] > last:
        return find1(nums[0], nums[1:], n+1 )
    else:
        return n

def findRecursive(nums):
    maxseq = 0
    for i in range(len(nums)):
        n = find1(nums[i], nums[i+1:], 1)
        if n > maxseq:
            maxseq = n
    return maxseq

print( findRecursive([1, 9, 3, 10, 4, 20, 2]))

使用 python 的递归方法中的最长递增子数组

longest increasing subarray in recursive method using python

python

recursion

dynamic-programming