通过最多两次买卖股票获得最大利润

在事务中，一个买主分别在早上和晚上买卖股票。如果一天最多允许两次事务。第二个事务只能在第一个事务完成后才能开始。如果给出了股票价格，则找到买方可以赚到的最大利润。

输入输出

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