C++で株式を売買した後の最大利益

この問題では、i日目の特定の株式の価格を示す配列stkprice[]が与えられます。私たちの仕事は、C++で株式を売買した後の最大利益を計算するプログラムを作成することです。

問題の説明 −ここでは、利益を得るためにいつ売買できるかを確認する必要があります。利益を得るには、株を安く買い、値上がりしたら売る必要があります。そして、ドロップが再び発生したときに同じことを繰り返します。

問題を理解するために例を見てみましょう

入力

stkprice[] = {120, 310, 405, 210, 150, 550}

出力

685

説明

1日目に購入して3日目に販売すると、285の利益が得られます。

この後、5日目に購入して6日目に販売すると、400の利益が得られます。

これにより、総利益は（400 + 285）=685

ソリューションアプローチ

簡単な解決策は、売買サイクルのすべての可能な組み合わせをチェックすることです。毎日から当日の最後の最初の販売までの購入と販売のサイクルの組み合わせを試してください。そして、その最大の利益を生み出すサイクルを取ります。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
int max(int a, int b){
   if(a > b)
      return a;
      return b;
}
int MaximizeProfit(int stkPrice[], int firstDay, int lastDay){
   if (lastDay <= firstDay)
      return 0;
   int maxProfit = 0;
   for (int i = firstDay; i < lastDay; i++) {
      for (int j = i + 1; j <= lastDay; j++) {
         if (stkPrice[j] > stkPrice[i]) {
            int profit = ( stkPrice[j] - stkPrice[i] ) + MaximizeProfit(stkPrice, firstDay, i - 1) + MaximizeProfit(stkPrice, j + 1, lastDay);
            maxProfit = max(maxProfit, profit);
         }
      }
   }
   return maxProfit;
}
int main(){
   int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
   int days = 6 ;
   cout<<"The Maximum profit is "<<MaximizeProfit(stkPrice, 0, days);
   return 0;
}

出力

The Maximum profit is 4196007

より効果的な解決策は、各取引の最大利益を見つけることによって、それらから最大利益を見つけることに基づいています。これは、取引日の極小値と極大値を見つけることによって行うことができます。極小値は、株価が前日と翌日の両方よりも低い時代です。 Andmaximaは最小値の反対です。極小値（index0からn-2以内）がない場合、その日数は利益を生むことができません。

利益を最大化するために、極小値で株式を購入し、次の極大値でそれを販売し、最小値と最大値のペアに対して同じことを行います。すべての最小値から最大値の利益を加算すると、maxProfitが得られます。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
void MaximizeProfit(int price[], int n){
   if (n == 1)
      return;
   int maxProfit = 0;
   int i = 0;
   while (i <= n - 1) {
      while ((i <= n - 2) && (price[i + 1] <= price[i]))
         i++;
         int minima = i++;
      while ((i < n) && (price[i] >= price[i - 1]))
         i++;
      int maxima = i - 1;
      maxProfit += (price[maxima] - price[minima] );
      // For displaying profit for one minima-maxima cycle
      //cout <<"Stock bought on day "<<(minima+ 1 )<<" and Sold
      on day "<<(maxima+1) <<" at a profit of "<<(price[maxima] - price[minima] )<<"\n";
   }
   cout<<"The maximized profit is "<<maxProfit;
}
int main(){
   int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
   int days = 6;
   MaximizeProfit(stkPrice, days);
   return 0;
}

出力

The maximized profit is 685