以下のような配列を考えてみましょう。
{1, 5, 3, 5, 4, 1}
サブアレイを選択するときは、サブアレイ内の最小数に減らします。たとえば、サブ配列{5, 3, 5}はになり{3, 3, 3}ます。ここで、サブアレイの合計は、結果のサブアレイの合計として定義されます。たとえば{5, 3, 5}、合計は3 + 3 + 3 = 9です。タスクは、任意のサブアレイから作成できる最大の合計を見つけることです。上記の配列の場合、最大の合計は12で、サブ配列によって与えられ{5, 3, 5, 4}ます。
この問題をO（n 2 ）よりも時間内に解決することは可能ですか？
これには、O(n) 時間で実行されるアルゴリズムがあると思います。最初にアルゴリズムの最適化されていないバージョンについて説明し、次に完全に最適化されたバージョンを示します。
簡単にするために、最初に、元の配列のすべての値が異なると仮定しましょう。これは一般的に正しいわけではありませんが、良い出発点となります。
アルゴリズムの背後にある重要な観察事項は次のとおりです。配列内の最小要素を見つけて、配列を 3 つの部分に分割します。つまり、最小値の左側にあるすべての要素、最小値の要素自体、および最小値の右側にあるすべての要素です。概略的には、これは次のようになります
+-----------------------+-----+-----------------------+
| left values | min | right values |
+-----------------------+-----+-----------------------+
重要な観察事項は次のとおりです。最適な値を与える部分配列を取得する場合、次の 3 つのいずれかが当てはまる必要があります。
これにより、この問題を解決するための優れた初期再帰アルゴリズムが得られます。
では、このアルゴリズムはどれほど効率的でしょうか? まあ、それは本当に最小要素がどこにあるかに依存します. 考えてみれば、線形作業を行って最小値を見つけてから、問題を 2 つのサブ問題に分割し、それぞれを再帰します。これは、クイックソートを検討したときに発生するのとまったく同じ繰り返しです。これは、最良のケースでは Θ(n log n) 時間かかることを意味します (最小要素が常に各半分の中間にある場合) が、最悪のケースでは Θ(n 2 ) 時間かかる場合 (最小値は常に純粋に左端または右端にあります。
ただし、私たちが費やしているすべての労力は、各サブ配列の最小値を見つけるために使用されていることに注意してください。これには、k 個の要素に対して O(k) の時間がかかります。これを O(1) 時間まで高速化できるとしたら? その場合、私たちのアルゴリズムが行う作業ははるかに少なくなります。より具体的には、O(n) の作業のみを行います。その理由は次のとおりです。再帰呼び出しを行うたびに、最小要素を見つけるために O(1) 作業を行い、配列からその要素を削除して、残りの部分を再帰的に処理します。したがって、各要素は最大 1 つの再帰呼び出しの最小要素になることができるため、再帰呼び出しの合計数は要素の数を超えることはできません。これは、それぞれが O(1) の作業を行う最大 O(n) 回の呼び出しを行い、合計で O(1) の作業を行うことを意味します。
では、この魔法のようなスピードアップを正確に得るにはどうすればよいのでしょうか? ここで、デカルト ツリーと呼ばれる、驚くほど用途が広く、あまり評価されていないデータ構造を使用します。デカルト ツリーは、次のプロパティを持つ一連の要素から作成されたバイナリ ツリーです。
たとえば、シーケンス4 6 7 1 5 0 2 8 3には次のデカルト ツリーがあります。
0
/ \
1 2
/ \ \
4 5 3
\ /
6 8
\
7
そして、ここで私たちは魔法を手に入れます。デカルト ツリーのルートを見るだけで、シーケンスの最小要素をすぐに見つけることができます。これには O(1) 時間しかかかりません。それが完了したら、再帰呼び出しを行い、最小要素の左側または右側にあるすべての要素を調べると、ルート ノードの左右のサブツリーに再帰的に下降しているだけです。は、これらのサブ配列の最小要素をそれぞれ O(1) 時間で読み取ることができることを意味します。気の利いた！
本当の美しさは、O(n) 時間で n 個の要素のシーケンスのデカルト ツリーを構築できることです。このアルゴリズムについては、ウィキペディアの記事のこのセクションで詳しく説明しています。これは、元の問題を解決するための超高速アルゴリズムを次のように取得できることを意味します。
全体として、これには O(n) 時間がかかり、O(n) スペースを使用します。これは、最初に使用した O(n 2 ) アルゴリズムよりも時間が改善されています。
この説明の最初に、すべての配列要素が個別であると仮定しましたが、これは実際には必要ありません。各ノードがその子よりも小さいという要件を変更して、各ノードがその子よりも大きくないという要件を変更することで、不明確な要素を含む配列のデカルト ツリーを構築できます。これは、アルゴリズムやそのランタイムの正確性には影響しません。これは、ことわざの「読者への演習」としておきます。:-)
これはクールな問題でした！これが役立つことを願っています！
数値がすべて負ではないと仮定すると、これは単に「ヒストグラムの長方形領域を最大化する」問題ではありませんか？今では有名になりました...
O（n）ソリューションが可能です。このサイト： http： //blog.csdn.net/arbuckle/article/details/710988にはたくさんのきちんとした解決策があります。
私が考えていることを詳しく説明するために（間違っている可能性があります）、各数値を幅1のヒストグラムの長方形と考えてください。
サブアレイ[i、j]を「最小化」して合計すると、基本的に、iからjにまたがるヒストグラムの長方形の領域が得られます。
これは以前にSOに表示されました：ヒストグラムの下の長方形の領域を最大化すると、コードと説明が表示され、公式ソリューションページ（http://www.informatik.uni-ulm.de/acm/Locals/2003/html ）へのリンクが表示されます。 /judge.html）。
私が試した次のアルゴリズムは、最初に配列をソートするために使用されるアルゴリズムの順序になります。たとえば、最初の配列が二分木ソートでソートされている場合、最良の場合は O(n)、平均の場合は O(n log n) になります。
アルゴリズムの要点:
配列がソートされます。ソートされた値と対応する古いインデックスが保存されます。二分探索木は、対応する古いインデックスから作成されます。これは、現在の値よりも小さい値に遭遇することなく前後に移動できる距離を決定するために使用されます。これにより、可能な最大のサブ配列が得られます。
質問の配列[1,5,3,5,4,1]での方法を説明します
1 5 3 5 4 1
-------------------------
array indices => 0 1 2 3 4 5
-------------------------
この配列はソートされています。値とそのインデックスを昇順で保存します。これは次のようになります。
1 1 3 4 5 5
-------------------------
original array indices => 0 5 2 4 1 3
(referred as old_index) -------------------------
値と古いインデックスの両方を参照することが重要です。連想配列のように。
明確にするためのいくつかの用語：
old_index は、要素の対応する元のインデックス (元の配列のインデックス) を参照します。
たとえば、要素 4 の場合、old_index は 4 です。current_index は 3 です。
一方、 current_index は、ソートされた配列内の要素のインデックスを参照します。current_array_value は、ソートされた配列内の現在の要素値を参照します。
pre は順不同の先行者を指します。succ は順不同の後継者を指します
また、最小値と最大値は、ソートされた配列の最初と最後の要素 (それぞれ min_value と max_value) から直接取得できます。
さて、ソートされた配列で実行するアルゴリズムは次のとおりです。
アルゴリズム：
一番左の要素から進みます。
ソートされた配列の左からの各要素に対して、このアルゴリズムを適用します
if(element == min_value){
max_sum = element * array_length;
if(max_sum > current_max)
current_max = max_sum;
push current index into the BST;
}else if(element == max_value){
//here current index is the index in the sorted array
max_sum = element * (array_length - current_index);
if(max_sum > current_max)
current_max = max_sum;
push current index into the BST;
}else {
//pseudo code steps to determine maximum possible sub array with the current element
//pre is inorder predecessor and succ is inorder successor
get the inorder predecessor and successor from the BST;
if(pre == NULL){
max_sum = succ * current_array_value;
if(max_sum > current_max)
current_max = max_sum;
}else if (succ == NULL){
max_sum = (array_length - pre) - 1) * current_array_value;
if(max_sum > current_max)
current_sum = max_sum;
}else {
//find the maximum possible sub array streak from the values
max_sum = [((succ - old_index) - 1) + ((old_index - pre) - 1) + 1] * current_array_value;
if(max_sum > current_max)
current_max = max_sum;
}
}
例えば、
元の配列は
1 5 3 5 4 1
-------------------------
array indices => 0 1 2 3 4 5
-------------------------
ソートされた配列は
1 1 3 4 5 5
-------------------------
original array indices => 0 5 2 4 1 3
(referred as old_index) -------------------------
最初の要素の後:
max_sum = 6 [1*6 に減少します]
0
2 番目の要素の後:
max_sum = 6 [1*6 に減少します]
0
\
5
3 番目の要素の後:
0
\
5
/
2
inorder トラバーサルの結果: 0 2 5
アルゴリズムを適用し、
max_sum = [((成功 - old_index) - 1) + ((old_index - pre) - 1) + 1] * current_array_value;
max_sum = [((5-2)-1) + ((2-0)-1) + 1] * 3 = 12
current_max = 12 [可能な最大値]
4 番目の要素の後:
0
\
5
/
2
\
4
inorder トラバーサルの結果: 0 2 4 5
アルゴリズムを適用し、
max_sum = 8 [これは 12 未満であるため破棄されます]
5 番目の要素の後:
max_sum = 10 [2 * 5 に減少、8 より小さいため破棄]
最後の要素の後:
max_sum = 5 [1 * 5 に減少、8 未満であるため破棄]
このアルゴリズムは、配列のソートに最初に使用されるアルゴリズムの順序になります。たとえば、最初の配列がバイナリ ソートでソートされている場合、最良の場合は O(n)、平均の場合は O(n log n) になります。
スペースの複雑さは O(3n) [O(n + n + n)、ソートされた値の n、古いインデックスの別の n、および BST の構築の別の n] になります。しかし、これについてはよくわかりません。アルゴリズムに関するフィードバックをお待ちしております。