algorithm - 要素の合計/数が最大の部分配列を見つける

Question

入力: n 個の正負の数値と数値 k の配列。

出力: 要素の最大合計を部分配列内の要素数で割った、少なくとも k 個の連続する要素の部分配列。

O(n^2) アルゴリズムは簡単です。誰かがこれのためのより良いアルゴリズムを持っていますか?

Answer 1

二分探索が使えます。

検索値についてはx、配列を検討してb[i] = a[i] - xください。ここで、少なくとも の長さの部分配列の合計の最大値を見つけますk。

長さの部分配列の平均は であるため、これkは機能し(a[p] + ... + a[p + k - 1]) / kます。したがって、次のようになります。

(a[p] + ... + a[p + k - 1]) / k >= avg
a[p] + ... + a[p + k - 1] >= avg * k
(a[p] - avg) + ... + (a[p + k - 1] - avg) >= 0

kしたがって、各要素からそれを減算することによって平均を二分探索する場合、長さが少なくとも の正和部分配列 (最大のものを見つけて、それが正かどうかを確認する) を見つけることができればavg、有効な答えです: に進みます。検索し[avg, max_avg]て、より良いものを見つけることができるかどうかを確認してください。そうでない場合は、検索を に減らします[0, avg]。