123 - Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

Say you have an array for which the i^th 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).

Hide Tags

Array Dynamic Programming

Hide Similar Problems

(M) Best Time to Buy and Sell Stock (M) Best Time to Buy and Sell Stock II (H) Best Time to Buy and Sell Stock IV

两次分析起来要复杂一些，似乎第一题的思路不能直接套过来。
但奥秘在于。。。分治（参考帖子）：
对于每一天，分别求出开始到这天（前半程），以及这天到结束（后半程）之间的最大利润，
然后对于比较每一天的前后半程之和来寻找两次买卖的最大利润即可。
这样问题就转化成了第一题了！！

但是这还不够，直接按照这个思路写的TLE了，原因是，对每个点，都跑一遍数组，复杂度是O(n²)，耗时太大。
所以还得上DP：
用辅助数组 pred[] 和 succ[]，分别向右/向左扫描数组，如果遇到最低/最高则更新最低/最高；
其他时候计算利润，并且取已知的最大值。
这样只需要线性扫描数组两遍，即可获取每一天的前半程后半程最大利润，从而完成比较得到两次交易的最大利润。
实测结果 8 ms，相当地快。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sz=prices.size();
        if(2>sz)
            return 0;
       
        //check possible max profit before & after day ii
        int pred[sz]={0}; int succ[sz]={0};
        int lowest=prices[0], highest=prices[sz-1];
        for(int ii=1; ii<sz; ++ii)
            lowest = min(lowest, prices[ii]),    pred[ii] = max(pred[ii-1], prices[ii]-lowest);

        for(int ii=sz-2; ii>=0; ii--)
            highest = max(highest, prices[ii]),    succ[ii] = max(succ[ii+1], highest - prices[ii]);

        //then find the best combination of before + after of ii
        int best=0;
        for(int ii=0; ii<sz; ++ii)
            best = max(best, pred[ii]+succ[ii]);

        return best;
    }
};
8 ms.