[LeetCode] 123.Best Time to Buy and Sell Stock III 買股票的最佳時(shí)間之三

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.

這道是買股票的最佳時(shí)間系列問(wèn)題中最難最復(fù)雜的一道，前面兩道 Best Time to Buy and Sell Stock 和 Best Time to Buy and Sell Stock II 的思路都非常的簡(jiǎn)潔明了，算法也很簡(jiǎn)單。而這道是要求最多交易兩次，找到最大利潤(rùn)，還是需要用動(dòng)態(tài)規(guī)劃Dynamic Programming來(lái)解，而這里我們需要兩個(gè)遞推公式來(lái)分別更新兩個(gè)變量local和global，我們其實(shí)可以求至少k次交易的最大利潤(rùn)，找到通解后可以設(shè)定 k = 2，即為本題的解答。我們定義local[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易并且最后一次交易在最后一天賣出的最大利潤(rùn)，此為局部最優(yōu)。然后我們定義global[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易的最大利潤(rùn)，此為全局最優(yōu)。它們的遞推式為：

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])

其中局部最優(yōu)值是比較前一天并少交易一次的全局最優(yōu)加上大于0的差值，和前一天的局部最優(yōu)加上差值中取較大值，而全局最優(yōu)比較局部最優(yōu)和前一天的全局最優(yōu)，代碼如下：

解法一：

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];
    }
};

下面這種解法用一維數(shù)組來(lái)代替二維數(shù)組，可以極大的節(jié)省了空間，由于覆蓋的順序關(guān)系，我們需要j從2到1，這樣可以取到正確的g[j-1]值，而非已經(jīng)被覆蓋過(guò)的值，參見(jiàn)代碼如下：

解法二：

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];
    }
};

我們?nèi)绻僭O(shè)prices數(shù)組為1, 3, 2, 9, 那么我們來(lái)看每次更新時(shí)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

其實(shí)上述的遞推公式關(guān)于local[i][j]的可以稍稍化簡(jiǎn)一下，我們之前定義的local[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易并且最后一次交易在最后一天賣出的最大利潤(rùn)，然后解釋了一下第 i 天賣第 j 支股票的話，一定是下面的一種：

1. 今天剛買的
那么 Local(i, j) = Global(i-1, j-1)
相當(dāng)于啥都沒(méi)干

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

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

但其實(shí)第一種情況是不需要考慮的，因?yàn)楫?dāng)天買當(dāng)天賣不會(huì)增加利潤(rùn)，完全是重復(fù)操作，這種情況可以歸納在global[i-1][j-1]中，所以我們就不需要max(0, diff)了，那么由于兩項(xiàng)都加上了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/

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(123.買股票的最佳時(shí)間之三)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)買股票的最佳時(shí)間之三內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論