arrays - 配列の残りの平均を最小化する連続した部分列を見つけますか?

Question

整数配列があるとしarr[0..n-1]ます。sub[i..j]配列の残りの部分の平均が最小になるような部分列(i > 0 かつ j < n - 1) を見つけます。

例：

arr[5] = {5,1,7,8,2};

を削除する{7,8}と、配列{5, 1, 2}は平均 2.67 (可能な限り最小) になります。

これは最長増加部分列の修正だと思いましたが、わかりませんでした。

ありがとう、

Answer 1

二分探索で平均値を求めてみましょう。

すべての要素の合計が S であるとします。

与えられた x について、i から j までを除くすべての要素の平均が x 以下になるような i と j が存在するかどうかを確認します。

これを行うには、arr のすべての要素から x を引きます。i から j までを除くすべての要素の合計がゼロ以下になるような i と j が存在するかどうかを確認する必要があります。これを行うには、現在の配列内のすべての要素の合計を見つけます: S' = S - x * n. したがって、i から j までの合計が S' 以上になるような i と j を見つけたいと考えています。それを行うには、合計が最大の部分配列を見つけましょう。そして、これはエレガントな Jay Kadane のアルゴリズムを使用して行うことができます: https://en.wikipedia.org/wiki/Maximum_subarray_problem

二分探索を終了するのはいつですか? 最大部分配列の合計がゼロ (または十分に近い) になる場合。

時間計算量: O(n log w), w - 二分探索の精度。