仲間たち、これは些細なタスクに対する明らかに最適ではない解決策を公開するというブログ「アルゴリズム」にとって恥ずかしいことです。 配列内のサブ配列要素の最大合計は、O（n）で検索されます！ ウィキペディアだけがこの仕事のために尊敬されるなら。
カットの下の通常のソリューション。
実際、「事前準備」するものは何もありません。 記事では、すべてが逆さまになっています。 引用は、「最大サブアレイ」問題を解決するために事前に準備されたデータです。 著者が解決した問題は、「最大サブアレイ」タスクに要約されません。 それどころか、「最大サブアレイ」問題の解決策は、著者がやろうとしたことに帰着します。 見つける必要があるのは、A [j] -A [i]が最大（または最小）になるような配列Aのインデックスi <= jです。
為替レートの値の差が最大である2つの日付を見つけるタスクは、それと間隔（0、j）で先行する最小最小A [i]との差が最大になるように、極大A [j]を見つけることに縮小されます。 これは動的プログラミングの典型的な例であり、実装も理解しやすく、作成者が指定したソリューションよりもはるかに短く見えます。
def find(A): currentMin = 1e308 currentMinIndex = None maxDiff = -1e308 bestResult = None for i, v in enumerate(A): if v < currentMin: currentMin, currentMinIndex = v, i if v - currentMin > maxDiff: maxDiff, bestResult = v - currentMin, (currentMinIndex, i) return bestResult, maxDiff
ここで、currenctMin、currentMinIndexは現在の最小見積値と間隔（0、i）のインデックスです。 i番目のステップで、現在の最良の結果が、現在のコース値とその前の最小コース（currentMin）の差と比較されます。 現在の差が大きい場合-最高として記録され、最後まで続きます。 数学言語：
maxDiff（0）=-無限大
maxDiff（i）= max（maxDiff（i-1）、A [i]-min（A [0：i]））、
ここで、min（A [0：i]）は0からiまでの間隔の最小値です。
参照：
前のトピック
最大サブアレイの問題
動的プログラミング
PS。 前のトピックがメインのトピックに至らなかった場合、別の記事で回答を公開しません。 許して