通过最多两次买卖股票获得最大利润
在事务中，一个买主分别在早上和晚上买卖股票。如果一天最多允许两次事务。第二个事务只能在第一个事务完成后才能开始。如果给出了股票价格，则找到买方可以赚到的最大利润。
输入输出
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