arrays - O（1）時間でソートされていない配列の2つのインデックス間の最大値を見つける

Question

ソートされていない配列では、（この配列を前処理できます）。O（1）時間で次の質問にどのように答えることができますか？インデックスiからjまでの最大値を見つけます

編集：前処理にはO（n）時間とO（n）オーダーの追加メモリが必要になる可能性があるため、頻繁に発生するクエリはO（1）時間で応答されます...

Answer 1

メモリの制約や前処理の制約はありませんか？考えられるすべての答えを含むO（n ²i ）テーブルを作成するだけです（つまり、との可能な値ごとに1つのエントリj）。このテーブルは、O（n ³）時間で単純に作成でき、最大値を増分的に計算することにより、非常に簡単にO（n ^{2 ）に下げることができます。}

Answer 2

この問題（範囲最小クエリ問題と呼ばれる）は解決されます（O（n）前処理、O（1）クエリ）。ウィキペディアから：

O（1）時間で後続のクエリに応答するには、O（n）時間の前処理で十分であることが知られています。結果として得られるスキームのスペースは、実際には非常に小さく、つまりO（n）ビットです（Fischer＆Heun（2007）を参照）。

RMQの問題は、問題とまったく同じです（「最小」を「最大」に置き換えるだけです）。アルゴリズムのスケッチと、その正確性およびメモリ/時間の保証の証明については、http：//wcipeg.com/wiki/RMQ#Cartesian_treesを参照してください。

実装の複雑さの昇順でこの問題を解決するために利用できるさまざまなオプションの概要については、このTopCoderチュートリアルも参照してください。

Answer 3

これは不可能です。O（n）を取る最大値を見つけるために配列をウォークオーバーするか、配列を並べ替える（O（n）よりも高価）か、すべての可能な範囲の最大値を決定することによって事前計算する必要があります。はO（n）よりも高価であり、非常に多くのメモリを必要とします。

Answer 4

前処理がO（1）より大きくなる可能性がない限り、不可能です。並べ替えの何が問題になっていますか？これは、O（n * log（n））（または基数ソートが許可されている場合は最大O（n））のみです。