數組：找到兩個數字，使得它們的總和在一些附加條件下爲最大

Question

給定一組數字和一個數字k，找到最大總和，以便如果您在索引i處選擇一個數字，則不應從索引中選擇任何數字i - K至索引i + K。

這個問題是在谷歌問我的朋友。我無法找出更好的解決方案，然後是天真的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 [1]，其中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。

排序前陣可能沒有針對問題