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

Question

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

这个问题是在谷歌向我的朋友提出的。我无法找到比天真的解决方案更好的解决方案O(n^2)。

Answer 1

您可以通过跟踪数组中第一个 iK-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 组合，这是在数组 A[0],..,A[iK-1] 的初始值中看到的最大值。

Answer 2

您可以修改此http://www.geekviewpoint.com/java/dynamic_programming/positive_subset_sum或http://www.geekviewpoint.com/java/dynamic_programming/max_subarray_sum。

该问题可能无法接受之前对数组进行排序