最大2回の株式の売買による最大利益

取引では、1人の買い手が朝と夕方にそれぞれ株式を売買します。 1日に最大2つのトランザクションが許可される場合。 2番目のトランザクションは、最初のトランザクションが完了した後にのみ開始できます。株価が示されている場合は、購入者が稼ぐことができる最大の利益を見つけます。

入力と出力

Input:
A list of stock prices. {2, 30, 15, 10, 8, 25, 80}
Output:
Here the total profit is 100. As buying at price 2 and selling at price 30.
so profit 28. Then buy at price 8 and sell it again at price 80.
So profit 72. So the total profit 28 + 72 = 100

アルゴリズム

findMaxProfit(pricelist, n)

入力- すべての価格のリスト、リスト内のアイテムの数。

出力- 最大の利益。

Begin
   define profit array of size n and fill with 0
   maxPrice := pricelist[n-1]          //last item is chosen

   for i := n-2 down to 0, do
      if pricelist[i] > maxPrice, then
         maxPrice := pricelist[i]
      profit[i] := maximum of profit[i+1] and maxProfit – pricelist[i]
   done

   minProce := pricelist[0]           //first item is chosen
   for i := 1 to n-1, do
      if pricelist[i] < minPrice, then
         minPrice := pricelist[i]
      profit[i] := maximum of profit[i-1] and (profit[i]+(pricelist[i] - minPrice))
   done

   return profit[n-1]
End

例

#include<iostream>
using namespace std;

int max(int a, int b) {
   return (a>b)?a:b;
}

int findMaxProfit(int priceList[], int n) {
   int *profit = new int[n];
   for (int i=0; i<n; i++)            //initialize profit list with 0
      profit[i] = 0;

   int maxPrice = priceList[n-1];        //initialize with last element of price list

   for (int i=n-2;i>=0;i--) {
      if (priceList[i] > maxPrice)
         maxPrice = priceList[i];

      profit[i] = max(profit[i+1], maxPrice - priceList[i]);     //find the profit for selling in maxPrice
   }

   int minPrice = priceList[0];            //first item of priceList as minimum

   for (int i=1; i<n; i++) {
      if (priceList[i] < minPrice)
         minPrice = priceList[i];

      profit[i] = max(profit[i-1], profit[i] + (priceList[i]- minPrice) );
   }

   int result = profit[n-1];
   return result;
}

int main() {
   int priceList[] = {2, 30, 15, 10, 8, 25, 80};
   int n = 7;
   cout << "Maximum Profit = " << findMaxProfit(priceList, n);
}

出力

Maximum Profit = 100