LeetCode: Best Time to Buy and Sell Stock III [123]

【称号】

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).

【题意】

给定一个数组prices, prices[i]表示第i天的股价。本题规定最多仅仅能买卖两次，问最大收益是多少

【思路】

分别计算买卖一次的最大收益maxProfit1和买卖2次的最大收益maxProfit2，然后求最大值。

买卖一次的解法已经有了，详见Best Time to Buy and Sell Stock。
买卖两次的话我们须要确定转折点在什么地方。即在第i天卖出，在第i+1天买入。为了得到最大值我们须要知道我在第i天卖出的最大收益是多少，在第i+1天买入的最大收入是多少。求每天卖出可获得的最大收益Best Time to Buy and Sell Stock中已经给出解法，仅仅须要one-pass就完毕。那么怎么计算每天买入可获得的最大收益呢？一样的，仅仅只是换了一个方向而已。

为此我们维护两个数组buyProfit, sellProfit， sellProfit[i]表示在第i天卖出能够获得最大收益。buyProfit[i]表示在第i天买入可获得最大收入。则两次买卖的最大收益maxProfit2=max(buyProfit[i]+sellProfit[i+1]) i=1,2,3,....n-3, 当中n为prices数组的长度。

【代码】

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int size=prices.size();
        if(size<=1)return 0;
        
        int*back=new int[size];
        int*front=new int[size];
        int maxProfit=0;
        int minPrice=prices[0];
        int maxPrice=prices[size-1];
		back[size-1]=front[0]=0;
        // 求出以i结尾的前半段区间上买卖一次可获得最大收益
		maxProfit=0;
        for(int i=1; i<size; i++){
            int profit=prices[i]-minPrice;
			if(profit>maxProfit)maxProfit=profit;
            front[i]=maxProfit;
            if(prices[i]<minPrice)minPrice=prices[i];
        }
        // 求出以i開始的后半段区间上买卖一次可获得最大收益
		maxProfit=0;
        for(int i=size-2; i>=0; i--){
			int profit=maxPrice-prices[i];
			if(profit>maxProfit)maxProfit=profit;
            back[i]= maxProfit;
            if(prices[i]>maxPrice)maxPrice=prices[i];
        }
		
        //求两次买卖的最大值
		maxProfit=0;
        for(int i=0; i<size; i++){
            if(i==size-1){
				if(front[i]>maxProfit)maxProfit=front[i];
			}
			else{
				if(front[i]+back[i+1]>maxProfit)maxProfit=front[i]+back[i+1];
			}
        }
        
        return maxProfit;
    }
};