python - 带限制条件的长度为 L 的子序列的最大和

Question

给定一个正整数数组。如何找到长度为 L 的子序列与 max其任意两个相邻元素之间的距离不超过 K 的总和

我有以下解决方案，但不知道如何考虑长度 L。

1 <= N <= 100000, 1 <= L <= 200, 1 <= K <= N

f[i] 包含以 i 结尾的子序列的最大和。

for i in range(K, N)
    f[i] = INT_MIN
    for j in range(1, K+1)
        f[i] = max(f[i], f[i-j] + a[i])
return max(f)

Answer 1

(编辑:稍微简化的非递归解决方案)

你可以这样做，只是为每次迭代考虑是否应该包含或排除该项目。

def f(maxK,K, N, L, S):
    if L == 0 or not N or K == 0:
        return S
    #either element is included
    included = f(maxK,maxK, N[1:], L-1, S + N[0]  )
    #or excluded
    excluded = f(maxK,K-1, N[1:], L, S )
    return max(included, excluded)


assert f(2,2,[10,1,1,1,1,10],3,0) == 12
assert f(3,3,[8, 3, 7, 6, 2, 1, 9, 2, 5, 4],4,0) == 30

如果N很长可以考虑改成table版本，也可以改成元组输入，使用memoization。

由于OP后来包含了N可以是100 000的信息，所以我们不能真正使用这样的递归解决方案。所以这是一个在 O(nKL) 中运行的解决方案，具有相同的内存要求:

import numpy as np

def f(n,K,L):
    t = np.zeros((len(n),L+1))

    for l in range(1,L+1):
        for i in range(len(n)):
            t[i,l] = n[i] + max( (t[i-k,l-1] for k in range(1,K+1) if i-k >= 0), default = 0 )

    return np.max(t)


assert f([10,1,1,1,1,10],2,3) == 12
assert f([8, 3, 7, 6, 2, 1, 9],3,4) == 30

非递归解决方案的解释。表t[ i, l ]中的每个单元格表示最大子序列的值，恰好有l个元素使用位置i的元素，并且只有位置i或更低位置的元素，元素之间的距离最多为K。

长度为 n 的子序列(在 t[i,1] 中的子序列必须只有一个元素 n[i] )

较长的子序列有 n[i] + 一个 l-1 个元素的子序列，该子序列最先开始至多 k 行，我们选择具有最大值的那个。通过这种方式迭代，我们确保已经计算出该值。

考虑到您只回顾最多 K 步，可以进一步提高内存力。