arrays - 数组:找到两个数字，使得它们的和在某些附加条件下为最大值

给定一组数字和一个数字k，求最大值，这样，如果在索引i中选择一个数字，就不应该从索引i - K中选择任何数字到索引i + K。
这个问题是谷歌问我朋友的我想不出比天真的人更好的解决办法。

最佳答案

您可以在O（n）中通过跟踪数组中的第一个i-k-1条目所看到的所有值的最大值来实现这一点。
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]的初始值中看到的最高值。

关于arrays - 数组:找到两个数字，使得它们的和在某些附加条件下为最大值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14462653/