LeetCode309 最佳买卖股票时机含冷冻期

发表于 | 分类于 |
字数统计: 234 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/description/

题面

给定一段时间内每天的股票价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。

思路

可以用状态机来解决这种复杂的状态转移问题，通过建立多个状态以及它们间的状态转移方式
推导出状态转移房产
如图，用四个状态来表示这一带冷却的股票交易

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) {
            return 0;
        }
        vector<int> buy(n), s1(n), sell(n), s2(n);
        buy[0] = s1[0] = -prices[0];
        for (int i = 1; i < n; i++) {
            buy[i] = s2[i - 1] - prices[i];
            s1[i] = max(s1[i - 1], buy[i - 1]);
            s2[i] = max(s2[i - 1], sell[i - 1]);
            sell[i] = max(s1[i - 1], buy[i - 1]) + prices[i];
        }
        return max(sell[n - 1], s2[n - 1]);
    }
};