Best Time to Buy and Sell Stock III

LeetCode #123

Description:

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

Example:

Note

Idea:

从左往右DP一次，记录在i之前（包括i）卖出的max profit。 从右往左DP一次，记录在i之后（包括i）买入的max profit。 都存在数组里。然后扫描，max_profit = max(max_profit, sell_profit[i]+buy_profit[i])。

Time: O(n)

Code:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2) return 0;

        int len = prices.size();
        vector<int> sell_profit(len, 0);
        vector<int> buy_profit(len, 0);

        int min_price=prices[0];
        for(int i=1; i<prices.size(); ++i){
            sell_profit[i] = max(sell_profit[i-1], prices[i]-min_price);
            if(prices[i]<min_price)
                min_price=prices[i];
        }    

        int max_price=prices[len-1];
        for(int i=len-2; i>=0; --i){
            buy_profit[i] = max(buy_profit[i+1], max_price-prices[i]);
            if(prices[i]>max_price)
                max_price=prices[i];
        }   

        int max_profit = 0;
        for(int i=0; i<len; i++){
            max_profit = max(max_profit, sell_profit[i]+buy_profit[i]);
        }

        return max_profit;
    }
};

Solution 2, 这个是调用一个general的函数来计算每一天的max profit，不是很好写。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2) return 0;

        int len = prices.size();
        vector<int> sell_profit = profitSequence(prices, 1, len, true);
        vector<int> buy_profit = profitSequence(prices, len-2, -1, false);

        int max_profit = 0;
        for(int i=0; i<len; i++){
            max_profit = max(max_profit, sell_profit[i]+buy_profit[i]);
        }

        return max_profit;
    }

    vector<int> profitSequence(const vector<int>& prices, int start, int end, bool flag_ascend) {
        vector<int> result(prices.size(), 0);

        if(prices.empty()) return result;

        int incr = flag_ascend? 1 : -1;
        int ind_start = flag_ascend? 0 : prices.size()-1;
        int cmp_price=prices[ind_start];
        int max_profit=0;

        for(int i=start; i!=end; i = i + incr){
            if(flag_ascend){
                if(prices[i]-cmp_price > max_profit){
                    max_profit = prices[i]-cmp_price;
                }
                if(prices[i]<cmp_price)
                    cmp_price=prices[i];                
            }
            else{
                if(cmp_price-prices[i] > max_profit){
                    max_profit = cmp_price-prices[i];
                }
                if(cmp_price<prices[i])
                    cmp_price=prices[i];
            }
            result[i] = max_profit;
        }

        return result;
    }
};