变化的点在于，你最多进行两次交易

前后缀分解，枚举分界点 https://www.acwing.com/video/1487/

https://www.acwing.com/solution/content/219/

这里是以第二次买入为分界点，划分为了两个互补关联的子问题，分别求最值

动态规划常见一个问题，就是 dp 数组的一个边界问题，我可以让 dp 数组的下标和 prices 数组对齐，但是这样就需要单独处理一些边界问题。代码如下。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> f(n);
        for (int i = 0, minp = INT_MAX; i < n; i ++) {
            if (i) f[i] = max(f[i - 1], prices[i] - minp);
            else f[0] = 0;
            minp = min(minp, prices[i]);
        }
        int res = 0;
        for (int i = n - 1, maxp = 0; i >= 0; i --) {
            if (i) res = max(res, f[i - 1] + maxp - prices[i]);
            else res = max(res, maxp - prices[i]);
            maxp = max(maxp, prices[i]);
        }
        return res;
    }
};

如果不想单独处理，可以 vector<int> f(n + 1) 代价就是 dp 数组的下标实际从 1 开始， prices 从 0 开始，两者下标不匹配

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> f(n + 1);
        for (int i = 1, minp = INT_MAX; i <= n; i ++) {
            f[i] = max(f[i - 1], prices[i - 1] - minp);
            minp = min(minp, prices[i - 1]);
        }
        int res = 0;
        for (int i = n, maxp = 0; i >= 1; i --) {
            res = max(res, f[i - 1] + maxp - prices[i - 1]);
            maxp = max(maxp, prices[i - 1]);
        }
        return res;
    }
};

P.S. 2分钟就写完了

动态规划

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

这道题目看解答AC了，收获就是了解了这样设置多个状态，然后分别处理每个状态的递归表达式。

Carl

一天一共就有五个状态，

1. 没有操作
2. 第一次买入 (今天买入 or 维持之前买入的状态)
3. 第一次卖出
4. 第二次买入