列表中每个元素之间（至少）相隔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

- nasamat

---

当我运行你的代码时，得到的结果是13而不是11。我看不出来它如何强制要求在被加总的数字之间至少有一个数字。 - Karin

所有的数字都是非负数吗？ - Abhishek Bansal

Answer 1

如果k是一个常数，那么可以使用空间复杂度为O(k)，时间复杂度为O(nk)的算法来解决这个问题，符合你所提出的要求。

该算法从位置k + 1到n循环（如果数组长度小于该值，则可以很明显地在O(k)内解决）。在每一步中，它维护一个长度为k + 1的数组best，使得best的第j个条目是迄今为止找到的最佳解决方案，其使用的最后一个元素至少位于当前位置的左侧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中最大的项。

- Ami Tavory

Answer 2

编辑：

我误解了问题，如果你需要在k个元素之间至少有“k”个元素，那么以下是一个O(n^2)的解决方案。

如果这些数字都是非负数，那么DP递归关系如下：

DP[i] = max (DP[j] + A[i]) For all j st 0 <= j < i - k 
      = A[i] otherwise.

如果数组中存在负数，我们可以使用Kadane算法的思想：

DP[i] = max (DP[j] + A[i]) For all j st 0 <= j < i - k && DP[j] + A[i] > 0
      = max(0,A[i]) otherwise.

- Abhishek Bansal

---

非常感谢，您提供的解决方案是正确的，但是举个例子，如果k=1，则它将总是将它们视为一种不同，因为在其他情况下，如果我们在它们之间留下多个空格，可能会得到更高的总和。 对不起，也许我的问题没有那么清楚，我应该写“在求和数字之间至少有k个元素”。 我刚刚编辑了问题。 - nasamat

Answer 3

这是按照Ami Tavory描述的算法的快速实现（据我理解）。它适用于任何序列，但如果您的列表全是负数，则最大和将为0（空子序列的总和）。

import collections

def max_sum_separated_by_k(iterable, k):
    best = collections.deque([0]*(k+1), k+1)
    for item in iterable:
        best.appendleft(max(item + best[-1], best[0]))
    return best[0]

这个算法的空间复杂度是O(k)，时间复杂度是O(N)。所有deque操作，包括在一端添加一个值（并隐式地从另一端移除一个值以保持长度限制）和从两端读取值，都是O(1)。

如果你想让该算法返回最大子序列（而不仅仅是其总和），你可以将deque的初始化更改为从空列表开始，而不是从0开始。然后在循环体中附加max([item] + best[-1], best[0], key=sum)。虽然这会使效率大大降低，因为它增加了O(N)的操作。

- Blckknght

---

如何显示最大子序列的索引，而不是值。 - Sam

Answer 4

不确定复杂度，但编码效率让我陷入了困境。

max([sum(l[i::j]) for j in range(k,len(l)) for i in range(len(l))])

（我已将list变量替换为l，以免与关键字重叠）。

- Aguy

---

这是不正确的。它只检查不同起始位置和等间距跳跃的等间隔子序列。最佳子序列不一定具有等间距跳跃。 - Ami Tavory