18

サイズ n の配列が与えられ、1 から n までの各 k について、サイズ k の連続する部分配列の最大和を求めます。

この問題には、時間計算量 O(N 2 ) と O(1) 空間の明らかな解があります。ルアコード:

array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
n = #array

function maxArray(k)
    ksum = 0
    for i = 1, k do
        ksum = ksum + array[i]
    end
    max_ksum = ksum
    for i = k + 1, n do
        add_index = i
        sub_index = i - k
        ksum = ksum + array[add_index] - array[sub_index]
        max_ksum = math.max(ksum, max_ksum)
    end
    return max_ksum
end

for k = 1, n do
    print(k, maxArray(k))
end

時間の複雑さが低いアルゴリズムはありますか? たとえば、O(N log N) + 追加メモリ。

関連トピック：

4

7 に答える 7

0

他の制約を追加しない場合、O(N²) よりも効率的なソリューションはないと思います。つまり、最大和部分配列を見つけたと判断するには、他のすべての部分配列を探索する以外に方法はありません。

したがって、最小複雑度の解は、指定された長さ N の配列の連続するサブ配列の総数である O(N²/2) で構成されます。

個人的には、動的プログラミングのアプローチでこれを実装します。アイデアは、部分的な結果のくさびを持ち、それらを使用してサブアレイの現在の合計を構築することです（全体の合計を計算する代わりに）。とにかく、これは「のみ」一定のスピードアップを提供するため、複雑さは O(N²/2)~O(N²) になります。

以下は疑似コードです - Lua を話せなくてごめんなさい

// here we place temporary results, row by row alternating in 0 or 1
int[2][N] sum_array_buffer
// stores the start of the max subarray
int[N] max_subarray_start
// stores the value
int[N] max_subarray_value

array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
// we initialize the buffer with the array (ideally 1-length subarrays)
sum_array_buffer[1] = array
// the length of subarrays - we can also start from 1 if considered
for k = 1 ; k <= (N); ++k:
    // the starting position fo the sub-array
    for j = 0; j < (N-k+1); ++j:
        sum_array_buffer[k%2][j] = sum_array_buffer[(k+1)%2][j] + array[j+k-1]
        if j == 0 || sum_array_buffer[k%2][j] > max_subarray_value[k]:
            max_subarray_value = sum_array_buffer[k%2][j]
            max_subarray_start[k] = j


for k = 1 ; k <= (N); ++k:
    print(k, max_subarray_value[k])

グラフィカルに:

ここに画像の説明を入力

于 2018-01-24T22:37:59.690 に答える
0

k 要素の現在のウィンドウの有用な要素のみを格納する容量 k の Dequeue Qi を作成します。要素は、現在のウィンドウにあり、現在のウィンドウの左側にある他のすべての要素よりも大きい場合に役立ちます。すべての配列要素を 1 つずつ処理し、現在のウィンドウの有用な要素を含むように Qi を維持します。これらの有用な要素はソートされた順序で維持されます。現在のウィンドウでは、Qi の前にある要素が最大で、Qi の後ろにある要素が最小です。

于 2018-02-02T18:29:36.560 に答える
-2

以下のプロセスがあなたを助けるかもしれません

1) 最初の k 個の要素を選択し、サイズ k の自己平衡二分探索木 (BST) を作成します。

2) i = 0 から n – k までのループを実行します。

…..a) BST から最大要素を取得し、それを出力します。

…..b) BST で arr[i] を検索し、BST から削除します。

…..c) arr[i+k] を BST に挿入します。

時間複雑度: ステップ 1 の時間複雑度は O(kLogk) です。ステップ 2(a)、2(b)、および 2(c) の時間複雑度は O(Logk) です。ステップ 2(a)、2(b)、および 2(c) は n-k+1 回実行されるループ内にあるため、完全なアルゴリズムの時間計算量は O(kLogk + (n-k+1)*Logk) です。 O(nLogk) と書くこともできます。

于 2015-06-01T09:50:16.190 に答える