[Hdp] lc123. 买卖股票的最佳时机 III(dp+前后缀分解)

文章目录

• • 1. 题目来源
  • 2. 题目说明
  • 3. 题目解析
  • • 方法一：前后缀分解

1. 题目来源

链接：lc123. 买卖股票的最佳时机 III

2. 题目说明

3. 题目解析

该股票问题：最多进行 2 笔交易，每笔交易不能重叠(指买入下支股票前需要将手中股票卖出)

股票问题四部曲：

[Edp] lc121. 买卖股票的最佳时机(dp)

[Edp] lc122. 买卖股票的最佳时机 II(dp+思维)

[Hdp] lc123. 买卖股票的最佳时机 III(dp+前后缀分解)

[Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)

采用两种思路：前后缀分解(专用于处理 2 次交易，或者和 2 相关的问题，是一个很常用的思路)、

dp

(

dp

在这大材小用，

dp

可以直接求出

k

次交易的最大收益情况)

方法一：前后缀分解

思路：

• 枚举的时候可以枚举两次交易的分界点，不妨将分界点取为第二次交易的买入时间，记为第

  i

  天
• 那么第一次交易就在

  1~i

  天，第二次交易就在第

  i

  天之后
• 问题转化为求解在这两个前后缀中各买入一次股票的最大值
• 这两个时间段是独立的，那么我们可以采用 [Edp] lc121. 买卖股票的最佳时机(dp) 的思想。在求解后缀最大价值的时候，可以反向扫描，保存

  i+1 ~ n

  的最大值，记为

  max

  ，这样利用最大值减去当前值就是能获得的最大价值。
• 还要预处理得到

  f(i-1)

  的值，代表

  1 ~ i-1

  段操作一次的最大收益，这个完全就和 [Edp] lc121. 买卖股票的最佳时机(dp) 一样。

  f(i) = max(pi - minp, f(i-1))

• 那么总的收益就是

  f(i-1) + max - i

经过前后缀分解，我们就将问题分解为两个完全独立的子问题。分别求取前后缀中的最值。可以通过预处理前后缀，然后枚举分界点即可。

总结： res += max{0，第 i 天的价格 - 前 i - 1 天的价格}

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> f(n + 2);                           // 枚举前缀，且预处理前缀最大收益，下标从1开始
        for (int i = 1, minp = INT_MAX; i <= n; ++i) {  // minp存前段最小值
            f[i] = max(f[i - 1], prices[i - 1] - minp); // f[i]有两种转移方式
            minp = min(minp, prices[i - 1]);            // 更新minp
        }

        int res = 0;
        for (int i = n, maxp = 0; i; --i) {             // 枚举分界点，动态计算后缀最大收益
            res = max(res, maxp - prices[i - 1] + f[i - 1]); // maxp存后端最大值
            maxp = max(maxp, prices[i - 1]);            // 更新maxp
        }
        return res;
    }
};