1. 概要

このチュートリアルでは、ほとんどの場合、製品を売買することによって最大の利益を見つける問題について説明します。 素朴なアプローチを提示し、それを改善してより良い解決策を取得します。

最後に、両方のアプローチとそれらをいつ使用するかを比較します。

2. 問題の定義

製品に関心があるとします。 この商品の価格は、数日前にお知らせします。 その日の価格はとして示されます。 したがって、sizeという名前の配列が与えられます。

ほとんどのトランザクションを実行できます。新しいトランザクションは、前のトランザクションが完了した後にのみ開始できます。 トランザクションとは、製品を売買するプロセスを意味します。

トレーディング戦略を最適に計画することで得られる最大の利益を見つけるよう求められています。

つまり、多くてもインデックスのペアを選択する必要があります。 ペアごとに、初日に購入し、先日販売します。

したがって、次の最大値を見つける必要があります。

   

そのような、ここで、販売日と見なされ、購入日と見なされます。

3. 素朴なアプローチ

3.1. 一般的なアイデア

この問題について考え始めましょう、私たちは日があります。 毎日、私たちは製品を購入することを決定するかもしれません。 商品を購入することにした場合は、その翌日を選択して商品を販売する必要があります。 トランザクションの数が時間を超えない限り、これを継続できます。 また、売れ残り商品がないことにも注意が必要です。

この問題は、動的プログラミングアプローチを使用して簡単に解決できます。

最初に、は、トランザクションを実行することによって最初の日から得ることができる最大の利益として定義しましょう。

当日は、2つの選択肢があります。

  1. スキップしてください。 したがって、 。 この日は何もしないので、すべての利益は前日から得られます。
  2. 以前に購入した製品を販売します。 この場合、この日の前に購入日を選択する必要があります 。 したがって、ここで、は購入日を示します。 当日購入して当日販売したので、利益に加算します。 また、売れ残った商品を2つ以上持ち込めないため、利益を増やしています。

3.2. 実装

このアプローチの実装を見てみましょう。

最初に、いくつかの初期化を行います。

  • 何日も取引しても利益がないからです。
  • 何日もの取引から利益が得られないからです。

その後、上記の式に従って動的計画法の配列を埋め始めます。

各ペア（、）について、最初は、当日は売りたくないと想定しています。 したがって、トランザクションを使用した場合、最初の日から得られる最大の利益であると見なします。 そして、当日商品を購入し、当日販売することで、より良い利益を上げようとしています。 したがって、可能な限りすべてを繰り返し、より良い利益を得ることができるかどうかを確認します。

最後に、 日後に可能なすべてのトランザクション数を繰り返し、最大の利益が得られるトランザクションを取得します。

このアプローチの複雑さはです。ここで、は日数であり、は許可されたトランザクションの最大数です。

4. より速いアプローチ

素朴なアプローチを改善してみましょう。

4.1. 一般的なアイデア

素朴なアプローチでは、計算時に可能な限りの購入日数を試しました。 ただし、可能な限り最大の日で十分です。 したがって、各ペアのこの最大値をできるだけ速く取得する方法を考えてみましょう。

深く考えれば、動的計画法でもこの問題を解決できることを示すことができます。

現在は固定されているので、すべての変数を保持する方程式を定義しましょう。

   

配列のプレフィックスごとにこの値を最大化していることがわかります。 プレフィックスがで、次のプレフィックスに移動した場合、範囲に追加される要素は要素のみです。 したがって、最大値は以前と同じままであるか、値で更新されます。

その結果、次の式を使用して、この値のプレフィックスの最大値を計算できます。

   

素朴なアプローチに戻ると、最大の利益は、当日をスキップするか、その日に製品を販売して、それを購入するのに最適な日を見つけることからでした。 これを要約する方程式を書くことができます：

   

この方程式を利用することで、最終結果を得ることができます。

   

使用する最終的な方程式が見つかったので、実装にジャンプできます。

4.2. 実装

Fasterアプローチの実装を見てみましょう。

素朴なアプローチと同じように、いくつかの初期化を行います。

  • ：取引のある日からの利益はありません。
  • ：何日も取引しても利益はありません。
  • ：これは、アルゴリズムが以前に購入せずに製品を販売することを防ぐためです。 その理由は、取引では何も売れないからです。
  • 。 これは、アルゴリズムが最初に購入せずに製品を販売するのを防ぐためでもあります。 その理由は、その日が存在しないからです。

その後、上記の式に従って動的配列（および）の入力を開始します。

各ペア（、）について、最初に、を入力する必要があります。 2つの選択肢があります。 当日購入するか、その前に購入するかのどちらかです。

次に、を入力する必要があります。 同様に、2つの選択肢もあります。 当日販売とさせていただきます。 結果として、を取得します。 それ以外の場合、当日は販売いたしません。

最後に、 日後に可能なすべてのトランザクション数を繰り返し、最大の利益が得られるトランザクションを取得します。

このアプローチの複雑さはです。ここで、は日数であり、は許可されたトランザクションの最大数です。

5. 比較

時間の複雑さを考慮すると、一般的に、より高速なアプローチの方が複雑さは低くなります。

ただし、特定のケースでは、メモリの複雑さを気にする場合、単純なアプローチを使用すると、消費するメモリが少なくなります。 一般的に、単純なアプローチは、より高速な方法と比較して、メモリの約半分を消費します。 その理由は、より高速なアプローチにアレイが含まれているためです。

6. 結論

このチュートリアルでは、ほとんどの場合、製品の売買による最大利益を計算する問題について説明しました。 まず、素朴なアプローチを紹介しました。

次に、理論的なアイデアとより高速なアプローチの実装について説明しました。

最後に、両方のアプローチの概要を比較し、それぞれをいつ使用するかを示しました。