python - 列表元素的最大总和，每个元素由(至少)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) 中解决)。在每一步，它都维护一个长度为 k + 1 的数组 best，这样 jbest 是迄今为止找到的最佳解决方案，因此它使用的最后一个元素至少在当前位置左侧 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，则每个“至少”部分移动 1，因此对于 j = 2, ..., k + 1，best[ j] = max(最佳[j], 最佳[j - 1])。最后，设置 best[1] = u。

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