时间戳

首页 > 解决方案 > 最大和增加子序列（但输出是一个列表）

python - 最大和增加子序列（但输出是一个列表）

问题描述

编写一个递归程序来查找构成给定数组的最大和子序列之和的元素列表，使得子序列中的整数按升序排序。

例如，如果输入是{1, 101, 2, 3, 100, 4, 5}，那么输出应该是[1,2,3,100]（1+2+3+100 是最高和）

我试过这个，但我认为它根本没有帮助（我还没有得到动态编程，我认为这段代码对我的问题没有帮助）。

s = [3, 1, 6, 2, 8, 10]
rez=[]
max_prev=0
for i in range(len(s)):
    if s[i]>max_prev:
        max_prev=s[i]
        rez.append(s[i])
print(rez)

标签： pythonalgorithmdata-structures

解决方案

您可以构建一个升序列表（即列表列表），然后使用 max() 获得总和最大的列表：

A = [1, 101, 2, 3, 100, 4, 5]

series = [A[:1]]
for a in A[1:]:
    more = [s+[a] for s in series if s[-1]<=a] # add series where ascending
    series.extend([[a]]+more)                  # each value starts a new series

result = max(series,key=sum)
print(result)
# [1, 2, 3, 100]

[编辑] 为了提高内存效率，您可以使用递归方法，在该方法中，您将跳过第一个元素的子集的最大值与包含使用它的子集相比（剩余元素大于第一个元素）。

def maxAscendingSum(A):
    if len(A)<2: return A
    skipping  = maxAscendingSum(A[1:])
    using     = A[:1] + maxAscendingSum([a for a in A[1:] if a>A[0]])
    return max((skipping,using),key=sum)

为了使递归函数更加高效，您可以使用记忆来跟踪以前的结果并避免多次执行相同的工作：

def maxAscendingSum(A,memo=None):
    if len(A)<2: return A
    if memo is None: memo = dict()
    key = tuple(A)
    if key not in memo:
        skipping  = maxAscendingSum(A[1:],memo)
        using     = A[:1] + maxAscendingSum([a for a in A[1:] if a>A[0]],memo)
        memo[key] =  max((skipping,using),key=sum)
    return memo[key]

推荐阅读