arrays - 配列: いくつかの追加条件で合計が最大になるような 2 つの数値を見つけます

Question

一連の数値と数値が与えられた場合、 index で数値を選択する場合、 index から index までの数値を選択しkないような最大合計を見つけます。ii - Ki + K

この問題は、Google で友人に尋ねられました。私はナイーブよりも優れた解決策を見つけることができませんO(n^2)。

Answer 1

O（n）でこれを行うには、配列の最初のiK-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と組み合わせます。これは、配列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を変更できる場合があります。

前に配列をソートすることは、質問には受け入れられない場合があります