列表元素的最大总和，每个元素由（至少）k 个元素分隔

Question

给定一个数字列表来找到时间复杂度为 o(n) 和空间复杂度为 o(1) 的非相邻元素的最大和，我可以使用这个：

sum1= 0
sum2= list[0]

for i in range(1, len(list)):
    num= sum1
    sum1= sum2+ list[i]
    sum2= max(num, sum2)

print(max(sum2, sum1))

此代码仅在 k = 1 [求和数之间只有一个元素] 时才有效，如何通过使用动态编程更改 k 值来改进它。其中 k 是求和数之间的元素数。例如：

列表 = [5,6,4,1,2] k=1 答案 = 11 # 5+4+2

列表 = [5,6,4,1,2] k=2 答案 = 8 # 6+2

列表 = [5,3,4,10,2] k=1 答案 = 15 # 5+10

Answer 1

可以用空间O(k)和时间O(nk)来解决这个问题。如果k是常数，则这符合您问题中的要求。

该算法从位置k + 1到n循环。（如果数组比那个短，显然可以在O(k) 中解决）。在每一步，它维护一个best长度为k + 1的数组，这样第j个条目best是迄今为止找到的最佳解决方案，这样它使用的最后一个元素至少是当前位置左侧的j 个。

初始化best是通过为其条目j设置数组中位置1, ..., k + 1 - j 中最大的非负条目来完成的。因此，例如，best[1]是位置1, ..., k 中最大的非负条目，并且best[k + 1]为 0。

当在数组的位置i时，是否使用元素i。如果使用，则best到目前为止相关的是best[1]，所以写u = max(best[1] + a[i], best[1])。如果未使用元素i，则每个“至少”部分移动一个，因此对于j = 2, ..., k + 1 , best[j] = max(best[j], best[j - 1]). 最后，设置best[1] = u。

在算法终止时，解是 中最大的项best。