有一个看起来完全不像是 slope trick 的题目，做法其实和本题是一致的。

CF865D ：给定股票价格序列，每天买一股、卖一股或者什么的都不做，要求最后一天结束时不持有股票，问最大利润。

这个问题等价于「求将价格序列调整为不增的序列的最小成本」。

CF865D 题解区只有反悔贪心做法，本题题解区的贪心基本都没讲反悔的事。但其实，本题的贪心也需要考虑反悔的问题，这也是需要插入两次的原因，也可能是很多读者困惑的原因。

至于这两个问题为什么等价，不是很好解释，这可能也是很多题解含糊其词的地方。

调整为不增之后，盈利一定为零，这是显然的。但是，对于一般的情况，这两个数值为什么相等，用自然语言说清楚，可能需要费一番功夫。

所以，本文补个简单的形式证明：（对序列边界处的处理略过，仅作为梗概）

将序列 $\{a_i\}$ 调整为不增的最小成本为

引入 Lagrange 乘子 $\lambda_i$ 之后，问题等价于

它进一步等价于对偶问题：

当然，这里处理了一下后面的求和项，把所有和 $b_i$ 相关的项放在一块了。

而且，内层的最小化问题

很好处理：要么 $|\lambda_{i}-\lambda_{i-1}|\le 1$ 时，最小值点就是 $b_i=a_i$，最小值为 $a_i(\lambda_i-\lambda_{i-1})$；要么 $|\lambda_{i}-\lambda_{i-1}|> 1$ 时，最小值为 $-\infty$。

因此，最后，问题等价为

如果将 $\lambda_i$ 理解为每日的持仓，那么 $\lambda_i-\lambda_{i-1}$ 就是当日的交易行为。对 $\lambda$ 的限制只有两条：

• 非负，亦即必须先买后卖；
• 差值不能大于一，即单日交易的最大单位为一。

同时，式子隐含条件，即初值 $\lambda_0=0$，这当然成立；问题对终值 $\lambda_n=0$ 的限制并不必要，因为最后持仓为正只会白白损失利润。

这就说明，调整序列非增的问题，正好等价于股票交易的问题。

希望对大家理解有用。