최대 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