首页 > 代码库 > leetcode第一刷_Best Time to Buy and Sell Stock III

leetcode第一刷_Best Time to Buy and Sell Stock III

这道题还是挺难的,属于我前面提到的,给个数组,线性时间找出个什么东西,虽然上面的两个买卖股票也是这类,不过相比之下稚嫩多了。有关至少至多的问题比较烦人,不好想,等再做一些题,可能会发现什么规律。这道题的情况还是比较少的,要么买卖了两次,要么一次。

买卖一次的情况,已经解决过了,现在分析买卖两次的情况。两次买卖之间是没有交叉的,即下一次买之前一定已经卖掉了。最容易想到,穷去分点,每个部分都按照买卖一次的方法做。好,恭喜,你已经走在超时的路上了。那么怎么办呢,有没有一种方法,在线性时间内,等我走到一个分点的时候,就能知道划分两次求出来的结果?

没错,辅助空间。先从头往后扫一遍,记录下以这个点为终点时的最大收入,然后从尾向头扫一遍,记录下以这个点为起点的最大收入。再对每个分点扫一遍,看看已他为起点终点算出来的交易收入是不是最优的。

思路是这样的,描述起来比较清晰,实现的时候还是有可以优化的地方的,例如你发现从尾向头扫描的结果根本不用一整个数组,只要保存好后一个位置的最优值就可以了,因为当前最优值只跟峰值与当前值以及过去最优相关。

代码如下,未优化空间:

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int len = prices.size();
        if(len <= 1)
            return 0;
        vector<int> phistory(len);
        vector<int> pfuture(len);
        int valley = prices[0], peak = prices[len-1];
        for(int i=1;i<len;i++){
            valley = min(valley, prices[i]);
            phistory[i] = max(phistory[i-1], prices[i]-valley);
        }
        int res = 0;
        for(int i=len-2;i>=0;i--){
            peak = max(peak, prices[i]);
            pfuture[i] = max(pfuture[i+1], peak-prices[i]);
            res = max(res, pfuture[i]+phistory[i]);
        }
        return res;
    }
};