Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
法I：把要求的东西profits设成状态。
第一次：从左往右扫描，同I一样记录下minimum value，不同的是，不仅要知道最大profit，还要记录下每个当前位置的profit（需要一个数组），为了之后与第二次扫描的结果相加。
第二次：从右往左scan，记录下maximum value, 计算profit，再加上之前第一次扫描从0到当前位置的profit，得到总的profit。
时间复杂度O(n) *2
class Solution {
public:
int maxProfit(vector<int> &prices) {
if(prices.empty()) return ;
int size = prices.size();
int maxProfit = ;
int* profits = new int [size]; //表示从0到i的最大利润
int* profits_from_last = new int [size]; //表示从i到size-1的最大利润
//initial status
profits[] = ;
int minValue = prices[];
//scan from start
for(int i = ; i< size; i++)
{
if(prices[i] < minValue) //save the minimum value
{
minValue = prices[i];
profits[i] = profits[i-];
}
else //caculate the profit from minimum value to currentand compare to previous maximum profit(profits[i-1])
{
profits[i] = max(prices[i]-minValue,profits[i-]);
}
}
//initial status
profits_from_last[size-] = ;
int maxValue = prices[size-];
//scan from last
for(int i = size-; i >= ; i--)
{
if(prices[i] > maxValue) //save the maximum value
{
maxValue = prices[i];
profits_from_last[i] = profits_from_last[i+];
}
else //caculate the profit from current to maximum value and compare to previous maximum profit(profits_from_last[i+1])
{
profits_from_last[i] = max(maxValue-prices[i],profits_from_last[i+]);
}
int profit = profits[i] + profits_from_last[i]; //calculate profits of two transactions
if(profit>maxProfit)
{
maxProfit = profit;
}
}
return maxProfit;
}
};Note：第二次scan不必存储每个状态，所以只需一个变量存储到目前为止第二次扫描的最大利润。
class Solution {
public:
int maxProfit(vector<int> &prices) {
if(prices.empty()) return ;
int size = prices.size();
int maxProfit = ;
int* profits = new int [size]; //表示从0到i的最大利润
int* profits_from_last = new int [size]; //表示从i到size-1的最大利润
//initial status
profits[] = ;
int minValue = prices[];
//scan from start
for(int i = ; i< size; i++)
{
if(prices[i] < minValue) //save the minimum value
{
minValue = prices[i];
profits[i] = profits[i-];
}
else //caculate the profit from minimum value to currentand compare to previous maximum profit(profits[i-1])
{
profits[i] = max(prices[i]-minValue,profits[i-]);
}
}
//initial status
int maxSecondProfits = ;
int maxValue = prices[size-];
//scan from last
for(int i = size-; i >= ; i--)
{
if(prices[i] > maxValue) //save the maximum value
{
maxValue = prices[i];
}
else //caculate the profit from current to maximum value and compare to previous maximum profit(maxSecondProfits)
{
maxSecondProfits = max(maxValue-prices[i],maxSecondProfits);
}
int profit = profits[i] + maxSecondProfits; //calculate profits of two transactions
if(profit>maxProfit)
{
maxProfit = profit;
}
}
return maxProfit;
}
};法II：进一步提升space efficiency。扫描一次，从而不用存储第一次交易的状态。
在扫描的时候，把当前点看作两次交易都完成的点，计算当前最大利润。
然后再依次更新把当前点看作第二次买入点的最大利润，看作第一次卖出点的最大利润，第一次买入点的最大利润，这些都为了在下一个循环用来更新状态。
所以，需要用4个变量存储到当前日为止第1/2次买入/卖出的利润最大值。
时间复杂度O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int dates = prices.size();
if(dates <= ) return ;
int hold1 = INT_MIN, hold2 = INT_MIN;//buy stock
int release1 = , release2 = ;//sell stock
for(int i = ; i < dates; i++){
release2 = max(release2, hold2+prices[i]);// The maximum if we've just sold 2nd stock so far.
hold2 = max(hold2, release1 - prices[i]); // The maximum if we've just buy 2nd stock so far.
release1 = max(release1, hold1+prices[i]);// The maximum if we've just sold 1nd stock so far.
hold1 = max(hold1, -prices[i]); // The maximum if we've just buy 1st stock so far.
}
return release2;
}
};