C++實現LeetCode(123.買股票的最佳時間之三)

Posted on by

[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 (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

這道是買股票的最佳時間系列問題中最難最復雜的一道，前面兩道 Best Time to Buy and Sell Stock 和 Best Time to Buy and Sell Stock II 的思路都非常的簡潔明瞭，算法也很簡單。而這道是要求最多交易兩次，找到最大利潤，還是需要用動態規劃Dynamic Programming來解，而這裡我們需要兩個遞推公式來分別更新兩個變量local和global，我們其實可以求至少k次交易的最大利潤，找到通解後可以設定 k = 2，即為本題的解答。我們定義local[i][j]為在到達第i天時最多可進行j次交易並且最後一次交易在最後一天賣出的最大利潤，此為局部最優。然後我們定義global[i][j]為在到達第i天時最多可進行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])

其中局部最優值是比較前一天並少交易一次的全局最優加上大於0的差值，和前一天的局部最優加上差值中取較大值，而全局最優比較局部最優和前一天的全局最優，代碼如下：

解法一：

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int n = prices.size(), g[n][3] = {0}, l[n][3] = {0};
        for (int i = 1; i < prices.size(); ++i) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= 2; ++j) {
                l[i][j] = max(g[i - 1][j - 1] + max(diff, 0), l[i - 1][j] + diff);
                g[i][j] = max(l[i][j], g[i - 1][j]);
            }
        }
        return g[n - 1][2];
    }
};

下面這種解法用一維數組來代替二維數組，可以極大的節省瞭空間，由於覆蓋的順序關系，我們需要j從2到1，這樣可以取到正確的g[j-1]值，而非已經被覆蓋過的值，參見代碼如下：

解法二：

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int g[3] = {0};
        int l[3] = {0};
        for (int i = 0; i < prices.size() - 1; ++i) {
            int diff = prices[i + 1] - prices[i];
            for (int j = 2; j >= 1; --j) {
                l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);
                g[j] = max(l[j], g[j]);
            }
        }
        return g[2];
    }
};

我們如果假設prices數組為1, 3, 2, 9, 那麼我們來看每次更新時local 和 global 的值：

第一天兩次交易：　　　　　　第一天一次交易：

local:　　  0 0 0 　　　　　　local:　　  0 0 0 

global:　　0 0 0　　　　　 　global:　　0 0 0

第二天兩次交易：　　　　　　第二天一次交易：

local:　　  0 0 2 　　　　　　local:　　  0 2 2 

global:　　0 0 2　　　　　 　global:　　0 2 2

第三天兩次交易：　　　　　　第三天一次交易：

local:　　  0 2 2 　　　　　　local:　　  0 1 2 

global:　　0 2 2　　　　 　　global:　　0 2 2

第四天兩次交易：　　　　　　第四天一次交易：

local:　　  0 1 9 　　　　　　local:　　  0 8 9 

global:　　0 2 9　　　　　 　global:　　0 8 9

其實上述的遞推公式關於local[i][j]的可以稍稍化簡一下，我們之前定義的local[i][j]為在到達第i天時最多可進行j次交易並且最後一次交易在最後一天賣出的最大利潤，然後解釋瞭一下第 i 天賣第 j 支股票的話，一定是下面的一種：

1. 今天剛買的
那麼 Local(i, j) = Global(i-1, j-1)
相當於啥都沒幹

2. 昨天買的
那麼 Local(i, j) = Global(i-1, j-1) + diff
等於Global(i-1, j-1) 中的交易，加上今天幹的那一票

3. 更早之前買的
那麼 Local(i, j) = Local(i-1, j) + diff
昨天別賣瞭，留到今天賣

但其實第一種情況是不需要考慮的，因為當天買當天賣不會增加利潤，完全是重復操作，這種情況可以歸納在global[i-1][j-1]中，所以我們就不需要max(0, diff)瞭，那麼由於兩項都加上瞭diff，所以我們可以把diff抽到max的外面，所以更新後的遞推公式為：

local[i][j] = max(global[i – 1][j – 1], local[i – 1][j]) + diff

global[i][j] = max(local[i][j], global[i – 1][j])

類似題目：

Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock

參考資料：

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

到此這篇關於C++實現LeetCode(123.買股票的最佳時間之三)的文章就介紹到這瞭,更多相關C++實現買股票的最佳時間之三內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：