Leetcode笔记（13）Best Time to Buy and Sell Stock III

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 ，找出一次交易的max很容易。找出两次的话，鉴于有You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).两次交易之间必然有一个分界，只要指定一个分界，两边各自O(n)，则O(n^2)的解法很直观：

class Solution {
public:
    int maxOneProfit(vector<int> &prices, int l, int end)
    {
        if (l >= end)
            return 0;
        int minprice = prices[l];
        int maxp = 0;
        for (int i=l; i<end; i++)
        {
            minprice = min(minprice, prices[i]);
            maxp = max(maxp, prices[i] - minprice);
        }
        return maxp;
    }

    int maxProfit(vector<int> &prices) {
        int maxp = 0;
        for (int i=0; i<prices.size(); i++)
            maxp = max(maxp, maxOneProfit(prices, 0, i) + maxOneProfit(prices, i, prices.size()));
        return maxp;
    }
};

但是这题会在大数据集上TLE，进一步思考： 分界都在valley，即前后值都比当前（系列）值大的情况， 如：3， 1， 2的1或者3,1,1,2的1,那么，我们可以减少二分的次数，只在valley处做判断，于是有了以下这段code：

class Solution {
public:
    int maxOneProfit(vector<int> &prices, int l, int end)
    {
        if (l >= end)
            return 0;
        int minprice = prices[l];
        int maxp = 0;
        for (int i=l; i<end; i++)
        {
            minprice = min(minprice, prices[i]);
            maxp = max(maxp, prices[i] - minprice);
        }
        return maxp;
    }

    int maxProfit(vector<int> &prices) {
        int maxp = 0;
        int i = 0;
        while (i + 1 < prices.size())
        {
            maxp = max(maxp, maxOneProfit(prices, 0, i) + maxOneProfit(prices, i, prices.size()));
            while (i+1< prices.size() && prices[i+1] >= prices[i])
                i++;
            while (i+1< prices.size() && prices[i+1] <= prices[i])
                i++;
        }
        return maxp;
    }
};

这一方法顺利地accepted，但是理论上worst case仍是O(n^2)。于是在网上找到了O(n)的思路：

方法仍然是二分法，但是在上面的过程中我们对于每个（或多个）i分别计算了左边和右边的最大收益，但实际上，i+1的最大收益是依赖于之前i的最大收益计算过程的，这个O(n)的divide 过程中，对于i之前的收益做了O(n)次重复计算。如果提前将这些值计算好，就能得到O(n)的算法，可以说是DP,也可以说就是提前计算记录

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty())
            return 0;
        vector<int> leftProfit(prices.size(), 0);
        vector<int> rightProfit(prices.size(), 0);
        int minPrice = prices[0];
        for (int i=1; i<prices.size(); i++)
        {
            minPrice = min(minPrice, prices[i]);
            leftProfit[i] = max(leftProfit[i-1], prices[i] - minPrice);
        }

        int maxPrice = prices.back();
        for (int i=int(prices.size())-2; i>=0; i--)
        {
            maxPrice = max(maxPrice, prices[i]);
            rightProfit[i] = max(rightProfit[i+1], maxPrice - prices[i]);
        }

        int maxp = leftProfit[int(prices.size())-1];
        for (int i=0; i+1<prices.size(); i++)
            maxp = max(maxp, leftProfit[i] + rightProfit[i+1]);
        return maxp;
    }
};

 经验教训：

• 要寻找更高效的算法时，可以从当前算法出发进行优化，寻找重复计算的部分，提前计算好。
• 动态规划不一定只运用在整个问题上，多种算法思路结合也可能效果很好，这个是DP+dive and conquer