このアプローチでは、のすべての可能な値をチェックしています。 したがって、これをブルートフォースアプローチと呼びます。
可能なすべてのペアとを反復処理し、常に開始して前進するようにします。 インデックスは、製品を購入した日を表します。 一方、インデックスは、製品を販売した日を表します。
したがって、まだ購入していない製品は販売できないため、最初から先に進んでいきます。
ペア（、）ごとに、すでに見つかった利益からより良い利益を得ることができるかどうかを確認します。 その場合、保存された利益を更新します。 また、購入を決定した日と販売を決定した日を保管しています。
最後に、保存された回答と、製品を売買する日の両方のインデックスを返します。
素朴なアプローチの複雑さはで、は日数です。
4. 動的計画法アプローチ
素朴なアプローチを改善してみましょう。
4.1. 一般的なアイデア
素朴なアプローチでは、可能なすべての日とのペアを試しました。 しかし、深く考えてみると、当日販売する場合は、販売する前に、購入する日数の中で最も安い価格を選択するのが常に最適であることがわかります。
したがって、各ステップで、現在のインデックスの前の最小値を格納する値を計算する必要があります。 動的計画法を使用して、値をすばやく計算しましょう。
インデックスの前に最低価格の値を計算し、インデックスに達したときに値を計算する必要があるとします。 最初の解決策は、範囲内のすべての値を反復処理し、それらの中で最小値を取得することです。
ただし、の前の値が範囲を表していることがわかります。 現在の範囲はであるため、前の範囲とのインデックスのみが異なることがわかります。
したがって、の前の値との間の最小値を取ることにより、範囲内の最小値を簡単に計算できます。
アイデアをよりよく説明するために、次の例を見てみましょう。
まず、前の範囲がまだないため、割り当てます。 その後、各インデックスについて、との前の値の間の最小値を取ります。
値の計算方法を示したので、それを使用して単純なアプローチを改善できます。
4.2. 実装
動的計画法アプローチの実装を見てみましょう。
配列全体を計算する代わりに、これまでの最小値を格納するという名前の変数を保持します。
各ステップで、現在の値がこれまでの最低価格よりも小さいかどうかを確認します。 その場合、との値を更新します。 最小値のインデックスを保存して、製品を購入する日を決定できるようにすることに注意してください。
その後、購入日が最も少ない現在の販売日が、保存されているよりも優れたソリューションを提供するかどうかを確認します。 もしそうなら、私たちはこれまでに得た利益を最高のものとして保存します。 また、インデックスを買い日として、インデックスを売り日として保存します。
最後に、保存された回答と、購入日と販売日の両方のインデックスを返します。
このアプローチの複雑さはで、は日数です。
5. 結論
このチュートリアルでは、一連の価格から最大の単一販売利益を見つける問題について説明しました。 最初に、私たちは素朴なアプローチを提示しました。 次に、動的計画法ソリューションを取得するためにそれを改善する方法を示しました。
