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

更新時間：2021年07月26日 15:27:14 作者：Grandyang

這篇文章主要介紹了C++實現(xiàn)LeetCode(123.買股票的最佳時間之三),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下

[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 的思路都非常的簡潔明了，算法也很簡單。而這道是要求最多交易兩次，找到最大利潤，還是需要用動態(tài)規(guī)劃Dynamic Programming來解，而這里我們需要兩個遞推公式來分別更新兩個變量local和global，我們其實可以求至少k次交易的最大利潤，找到通解后可以設定 k = 2，即為本題的解答。我們定義local[i][j]為在到達第i天時最多可進行j次交易并且最后一次交易在最后一天賣出的最大利潤，此為局部最優(yōu)。然后我們定義global[i][j]為在到達第i天時最多可進行j次交易的最大利潤，此為全局最優(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ù)組來代替二維數(shù)組，可以極大的節(jié)省了空間，由于覆蓋的順序關系，我們需要j從2到1，這樣可以取到正確的g[j-1]值，而非已經(jīng)被覆蓋過的值，參見代碼如下：

解法二：

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)绻僭Oprices數(shù)組為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