[LeetCode 123] 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).

Diffculty
Hard

Analysis

分析1：这道题是Best Time to Buy and Sell Stock的扩展，现在我们最多可以进行两次交易。我们仍然使用动态规划来完成，事实上可以解决非常通用的情况，也就是最多进行k次交易的情况。这里我们先解释最多可以进行k次交易的算法，然后最多进行两次我们只需要把k取成2即可。我们还是使用“局部最优和全局最优解法”。我们维护两种变量，一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]），另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少（local[i][j]）。下面我们来看递推式，全局的比较简单： global[i][j] = max(local[i][j], global[i-1][j])，也就是去当前局部最好的，和过往全局最好的中大的那个（因为最后一次交易如果包含当前天一定在局部最好的里面，否则一定在过往全局最优的里面）。对于局部变量的维护，递推式是 local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)，也就是看两个变量，第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），第二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了）。上面的算法中对于天数需要一次扫描，而每次要对交易次数进行递推式求解，所以时间复杂度是O(n*k)，如果是最多进行两次交易，那么复杂度还是O(n)。空间上只需要维护当天数据皆可以，所以是O(k)，当 k = 2，则是O(1)。代码如下：

int maxProfit(vector &prices) { int n = prices.size(); if(n == 0) return 0; int[] local = new int[3]; int[] global = new int[3]; for(int i = 0; i < prices.length - 1; i++){ int diff = prices[i + 1] - prices[i]; for(int j = 2; j >= 1; j--){ local[j] = Math.max(global[j-1] + (diff > 0 ? diff : 0), local[j] + diff); global[j] = Math.max(local[j], global[j]); } } return global[2]; }

可以看到，这里的模型是比较复杂的，主要是在递推式中，local和global是交替求解的。不过理清思路之后，代码是非常简练的，不禁感叹算法真是牛逼哈，这么个复杂生活问题几行代码就解决了。

分析2：参考了Code Ganker的解法。这道题是Best Time to Buy and Sell Stock的扩展，现在我们最多可以进行两次交易。使用动态规划来完成，事实上可以解决非常通用的情况，也就是最多进行k次交易的情况。这里我们先解释最多可以进行k次交易的算法，然后最多进行两次我们只需要把k取成2即可。我们还是使用“局部最优和全局最优解法”。我们维护两种量，一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]），另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少（local[i][j]）。

下面我们来看递推式，全局的比较简单，

global[i][j]=max(local[i][j], global[i-1][j])，也就是去当前局部最好的，和过往全局最好的中大的那个（因为最后一次交易如果包含当前天一定在局部最好的里面，否则一定在过往全局最优的里面）。

对于局部变量的维护，递推式是: local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff),

也就是看两个量，第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），第二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local[i-1][j]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了）。

如果上面不好理解，可以这样理解：对于局部变量，第i天最多进行j次交易，可以分两种情况：一是这第j次交易就是当天买入当天卖出的，那么最大收益就是 global[i - 1][j - 1] + max(diff, 0), diff为第i天当天股价变化。另一种情况是：第j次交易早就买入了，但是拖到第i天当天才卖出。这种情况分析起来有点绕，但是可以视为：第i-1天卖出的收益 + 第i天当天的股价变化，所以就是local[i-1][j] + diff. 这样想就好懂了。

一维DP： int maxProfit(int[] prices) { if(prices==null || prices.length==0) return 0; int[] local = new int[3]; int[] global = new int[3]; for(int i = 0; i < prices.length-1; i++){ int diff = prices[i+1] - prices[i]; for(int j = 2; j >= 1; j--){ local[j] = max(global[j-1] + (diff > 0 ? diff:0), local[j] + diff); global[j] = max(local[j], global[j]); } } return global[2]; }

上面的算法中对于天数需要一次扫描，而每次要对交易次数进行递推式求解，所以时间复杂度是O(n*k)，如果是最多进行两次交易，那么复杂度还是O(n)。空间上只需要维护当天数据皆可以，所以是O(k)，当k=2，则是O(1)。

二维DP： class Solution { public: int maxProfit(vector& prices) { return helper(prices, 2); }

int helper(vector<int> prices, int k) {
    int len = prices.size();
    if (len == 0) return 0;
    int[len][k+1] local;
    int[len][k+1] global;
    for (int i = 1; i < len; i++) {
        int diff = prices[i] - prices[i-1];
        for (int j = 1; j <= k; j++) {
            local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff);
            global[i][j] = max(local[i][j], global[i-1][j]);
        }
    }
    return global[len-1][k];
}

};

// 洗刷刷思路：Best Time to Buy and Sell Stock III III是这三题中最难的。允许两次买卖，但同一时间只允许持有一支股票。也就意味着这两次买卖在时间跨度上不能有重叠（当然第一次的卖出时间和第二次的买入时间可以是同一天）。既然不能有重叠可以将整个序列以任意坐标i为分割点，分割成两部分：

prices[0:n-1] => prices[0:i] + prices[i:n-1]

对于这个特定分割来说，最大收益为两段的最大收益之和。每一段的最大收益当然可以用I的解法来做。而III的解一定是对所有0<=i<=n-1的分割的最大收益中取一个最大值。为了增加计算效率，考虑采用dp来做bookkeeping。目标是对每个坐标i：

计算A[0:i]的收益最大值：用minPrice记录i左边的最低价格，用maxLeftProfit记录左侧最大收益
计算A[i:n-1]的收益最大值：用maxPrices记录i右边的最高价格，用maxRightProfit记录右侧最大收益。
最后这两个收益之和便是以i为分割的最大收益。将序列从左向右扫一遍可以获取1，从右向左扫一遍可以获取2。相加后取最大值即为答案。

class Solution { public: int maxProfit(vector& prices) { int n = (int)prices.size(); if(n <= 1) return 0; int minPrices = prices[0]; int maxProfitLeft[n] = {0}; int maxprofit = 0; for(int i = 1; i < n; ++i){ minPrices = min(minPrices, prices[i - 1]); maxprofit = max(maxprofit, prices[i] - minPrices); maxProfitLeft[i] = maxprofit; }

    int res = maxProfitLeft[n - 1];
    int maxPrices = prices[n - 1];
    maxprofit = 0;
    for(int i = n - 2; i >= 0; --i){
        maxPrices = max(maxPrices, prices[i + 1]);
        maxprofit = max(maxprofit, maxPrices - prices[i]);
        if(res < maxprofit + maxProfitLeft[i])
            res = maxprofit + maxProfitLeft[i];
    }

    return res;
}

};

分析：这一题约束最多只能买卖两次股票，并且手上最多也只能持有一支股票。因为不能连续买入两次股票，所以买卖两次肯定分布在前后两个不同的区间。设p(i) = 区间[0,1,2...i]的最大利润 + 区间[i,i+1,....n-1]的最大利润（式子中两个区间内分别只能有一次买卖，这就是第一道题的问题），那么本题的最大利润 = max{p[0],p[1],p[2],...,p[n-1]}。根据第一题的算法2，我们可以求区间[0,1,2...i]的最大利润；同理可以从后往前扫描数组求区间[i,i+1,....n-1]的最大利润，其递归式如下： dp[i-1] = max{dp[i], maxprices - prices[i-1]}, maxprices是区间[i,i+1,...,n-1]内的最高价格。

class Solution { public: int maxProfit(vector &prices) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. const int len = prices.size(); if(len <= 1) return 0; int maxFromHead[len]; maxFromHead[0] = 0; int minprice = prices[0], maxprofit = 0; for(int i = 1; i < len; i++){ minprice = min(prices[i-1], minprice); if(maxprofit < prices[i] - minprice) maxprofit = prices[i] - minprice; maxFromHead[i] = maxprofit; } int maxprice = prices[len - 1]; int res = maxFromHead[len-1]; maxprofit = 0; for(int i = len-2; i >= 0; i--){ maxprice = max(maxprice, prices[i+1]); if(maxprofit < maxprice - prices[i]) maxprofit = maxprice - prices[i]; if(res < maxFromHead[i] + maxprofit) res = maxFromHead[i] + maxprofit; } return res; } };

A new problem of completing at most m transactions can be efficiently solved by using the method below. The profit of one transaction is price[i] - price[j] where i > j. We then can rewrite the expression to be: price[i] - price[i-1] + price[i-1] - price[i-2] + ... + price[j+1] - price[j]. If we construct an array of {diff[i]} = {price[i+1] - price[i]}, then the problem can be reduced to the maximum m segments sum problem on diff[], where m = 2 in this case. Then we can play the fancy dynamic programming to solve it.

Here is one solution of the maximum m segments sum problem. The running time is O(NM). Let f[i][j] to be the maximum sum of j segments from the first i numbers, where the last element we choose is a[i]. We have two strategies to achieve it:

Choosing the optimal j-1 segments from the first k numbers, and starting a new segment with a[i]: f[i][j] = f[k][j-1] + a[i], where j-1 <= k <= i-1.

However, f[k][j-1] is the subproblems that we've already solved. If we memorize the optimal j - 1 segments, namely g[j-1] = max(f[k][j-1]), the state transition can be achieved in O(1):

f[i][j] = g[j-1] + a[i]

Appending a[i] to the last segment in the first i-1 numbers f[i][j] = f[i-1][j] + a[i].

Here is why we must choose a[i] in our strategies. If f[i-1][j] is not ends at a[i-1], then appending a[i] to f[i-1][j] will get j+1 segments, which violates the definition of f[i][j]. class Solution { public: int maxProfit(vector &prices) { int f[3] = {0}; int g[3] = {0};

        int n = prices.size() - 1;
        for (int i = 0; i < n; ++i) {
            int diff = prices[i+1] - prices[i];
            int m = min(i+1, 2);
            for (int j = m; j >= 1; --j) {
                f[j] = max(f[j], g[j-1]) + diff;
                g[j] = max(g[j], f[j]);
            }
        }
        return max(g[1], g[2]);
    }
};

1.49 (123) Best Time to Buy and Sell Stock III

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

Analysis

results matching ""

No results matching ""