問題設定者のアプローチは指数関数的に複雑です。N=30 にしてはかなり良いです。しかし、より大きなサイズの場合はそうではありません。指数時間解を見つける方が面白いと思います。そして、O(N 4 ) の複雑さを持つものを見つけました。
このアプローチは、最適解が連続する最大要素のいくつかのグループから始まり、配列全体が最大値で満たされるまでこの単一のグループのみを拡張するという事実を使用します。
この事実を証明するには、連続する最大要素の 2 つの開始グループを取り、それらが 1 つのグループに統合されるまで最適な方法でそれぞれを拡張します。グループ 1 がサイズ M に成長するために X ターンを必要とし、グループ 2 が同じサイズ M に成長するために Y ターンを必要とし、ターン X + Y + 1 でこれらのグループがマージするとします。結果は、少なくとも M * 4 のサイズのグループです。ここで、グループ 2 のターン Y の代わりに、グループ 1 の追加のターン X + 1 を作成します。この場合、グループのサイズは、少なくとも M * 2 で、最大 M / 2 です。 (最初に最大要素を数えたとしても、それはステップ Y に含まれる可能性があります)。この変更の後、ターン X + Y + 1 で、マージされたグループのサイズは、最初のグループ拡張の結果として少なくとも M * 4 になり、これに 2 番目のグループから少なくとも 1 つの要素が追加されます。したがって、ここで単一のグループを拡張すると、同じステップ数でより大きなグループが生成されます (Y > 1 の場合、必要な手順も少なくて済みます)。これはグループ サイズ (M) が等しい場合に機能するため、等しくないグループの場合はさらに効果的です。この証明は、いくつかのグループ (2 つ以上) の場合に拡張できます。
連続する最大要素の 1 つのグループを操作するには、グループの開始位置と終了位置の 2 つの値のみを追跡する必要があります。つまり、三角行列を使用してすべての可能なグループを格納できるため、動的計画法アルゴリズムを使用できます。
擬似コード:
For each group of consecutive maximal elements in original array:
Mark corresponding element in the matrix and clear other elements
For each matrix diagonal, starting with one, containing this element:
For each marked element in this diagonal:
Retrieve current number of turns from this matrix element
(use indexes of this matrix element to initialize p1 and p2)
p2 = end of the group
p1 = start of the group
Decrease p1 while it is possible to keep median at maximum value
(now all values between p1 and p2 are assumed as maximal)
While p2 < N:
Check if number of maximal elements in the array is >= N/2
If this is true, compare current number of turns with the best result \
and update it if necessary
(additional matrix with number of maximal values between each pair of
points may be used to count elements to the left of p1 and to the
right of p2)
Look at position [p1, p2] in the matrix. Mark it and if it contains \
larger number of turns, update it
Repeat:
Increase p1 while it points to maximal value
Increment p1 (to skip one non-maximum value)
Increase p2 while it is possible to keep median at maximum value
while median is not at maximum value
アルゴリズムを単純にするために、グループが位置 0 で開始するか、位置 N で終了し、初期化をスキップし、最適化を行わなかった特殊なケースについては言及しませんでした。