LeetCode 188 Best Time to Buy and Sell Stock IV

Tag: 股票问题 LeetCode Posted on 2022-02-03 23:57:56 Edited on 2022-02-05 16:52:38 Views: 158

题目分析

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

分析可知,我们应仅当在谷底处买入,谷峰处卖出股票,期间可以有波动,但是不能低于起始处。

我们首先找出所有满足上述条件的最优买入卖出段,之后排序求出最大的 k 个的和即可。


以上分析有一处错误,期间可以有波动,实际上波动前后分两次买卖可以比一次买卖赚更多。

补救方法是,将波动视为一次买入卖出段,也参与排序。

但是这样搞之后,算法变得复杂,我们需要在 one pass 中记录这种波动的幅度。

不想再继续搞的有问题解法

三连 WA,有毒吧,不玩了,睡觉了。

https://leetcode.com/submissions/detail/633771632/

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<int> profits;
        int buy = prices[0];
        int sell = buy;
        bool downing = false;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] < buy) {
                downing = false;
                if (sell - buy > 0) {
                    profits.push_back(sell - buy);
                }
                buy = prices[i];
                sell = buy;
            } else if (prices[i] > sell) {
                if (downing) {
                    downing = false;
                    profits.push_back(sell - prices[i - 1]);
                }
                sell = prices[i];
            } else if (prices[i] < sell) {
                downing = true;
            }
        }
        if (sell - buy > 0) {
            profits.push_back(sell - buy);
        }
        sort(profits.rbegin(), profits.rend());
        int ans = 0;
        for (int i = 0; i < profits.size() && i < k; i++) {
            ans += profits[i];
        }
        return ans;
    }
};

动态规划法

参考 https://labuladong.gitee.io/algo/1/12/

  1. 状态:第一个是天数,第二个是允许交易的最大次数,第三个是当前的持有状态
  2. 选择:买入、卖出、无操作
  3. base case:实际上只需要处理第 0 天时已经持有股票的情况。

实现中,我为了清晰期间 dp 数组的索引直接与对应的意义对应,不需要再减一,但是我忘了 prices 可不是这样搞的,看了好久才发现这个 bug。

下面的一个优化是 k 实际上可以缩小成 d / 2,因为就算没有人为限制交易次数,天数依然会对其进行限制。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // state: day d, used times t, 1 / 0 have stock or not
        vector<vector<vector<int>>> dp(prices.size() + 1, vector<vector<int>>(k + 1, vector<int>(2, 0)));
        for (int t = 0; t <= k; t++) {
            dp[0][t][1] = INT_MIN;
        }

        for (int d = 1; d <= prices.size(); d++) {
            for (int t = 1; t <= k; t++) {
                dp[d][t][0] = max(dp[d-1][t][0], dp[d-1][t][1] + prices[d - 1]);
                dp[d][t][1] = max(dp[d-1][t][1], dp[d-1][t-1][0] - prices[d - 1]);
            }
        }
        int ans = 0;
        for (int i = 0; i <= k; i++) {
            ans = max(ans, dp[prices.size()][i][0]);
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/