C++实现LeetCode(123.买股票的最佳时间之三)

程序员文章站 2022-03-03 11:08:05

[leetcode] 123.best time to buy and sell stock iii 买股票的最佳时间之三say you have an array for which the...

[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