数组:在一些附加条件下找到两个数字，使其总和最大

Question

给定一组数字和一个数字k，找到最大总和，这样如果您在索引i处选择一个数字，则不应从索引i中选择任何数字i - K 到索引 i + K。

这个问题是在google上问我的 friend 的。我无法找出比天真的 O(n^2) 更好的解决方案。

Answer 1

通过跟踪数组中前 i-K-1 条目中看到的所有值的最大值，您可以在 O(n) 内完成此操作。

Python 代码:

A=[3,9,10,3,6,7,1,5]
K=2
m=A[0]
bestsum=0
for i in xrange(K+1,len(A)):
    m=max(A[i-K-1],m) # stores maximum of values in A[0],A[1],...,A[i-K-1]
    bestsum=max(bestsum,A[i]+m)
print bestsum

对于每个索引 i，我们将 A[i] 与 m 结合起来，m 是数组 A[0],..,A[i-K-1] 的初始值中看到的最高值。