反悔贪心：每天可以买进一股/卖出一股/不操作的股票问题

摘要: 反悔贪心的一种实现：通过精巧的公式设计，跟着贪心策略可以自动执行反悔

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 反悔贪心与反悔堆的思想，带截止时间的任务选择问题 中我们介绍了反悔贪心的思想，以及利用该思想解决带截止时间的任务选择的一类问题。

在文章 带约束条件的TopK选择问题，反悔贪心的思想 中，我们解决了几个 TopK 选择的问题，其算法都可以通过反悔贪心的思想去理解。

本文我们继续看一个经典问题，即买卖股票问题。根据一个贪心策略维护全局最优解，这需要用到一个堆。而反悔操作通过精巧的公式设计自动实现，其大致思想如下：

比如最大差值应该为 $p[j] - p[i]$，但按照贪心策略我们做出的是 $p[k] - p[i]$ 的选择，后续当我们发现 $p[j] - p[i]$ 更好时，按通常反悔操作的思路，我们是先将 $p[k] - p[i]$ 从答案中减去，再在答案中加上 $p[j] - p[i]$。但将减去和加上的部分合在一起，我们直接加上 $p[j] - p[k]$ 就相当于做了反悔操作。

股票问题：每天可买一股/卖一股/不操作

• Buy Low Sell High

给出接下来 N 天的股票，每天可以买进一股，卖出一股，或者什么也不做。N 天后，你的股票应该为零。

问这 N 天最多赚多少钱。

输入:
第一行一个整数天数N(2<=N<=300000).
第二行N个数字p1,p2...pN(1<=pi<=10^6),表示每天的价格.

输出: N天结束后能获得的最大利润.

输入输出样例
输入
9
10 5 4 7 9 12 6 2 10
输出
20
解释：分别在价格为5,4,2的时候买入,分别在价格为9,12,10的时候卖出

输入
20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
输出
41

算法：反悔贪心

首先考虑一种贪心策略：对于第 $k$ 天，如果可以卖出，则选择此前价格最小的一天 $i$，若 $p[i] < p[k]$，则卖出，对总利润贡献 $p[k] - p[i]$。这样我们可以用一个堆来维护第 $k$ 天以前可以买入的价格即可。

假设我们在 $i$ 日买入，对应于 $i$ 日买入的最优卖出日期为 $j$。但在第 $k$ 日（尚未枚举到 $j$）时我们就发现卖出可以挣钱，则按贪心策略，在 $k$ 日卖出，对总利润贡献 $p[k] - p[i] > 0$。

将 $p[k] - p[i]$ 加入总利润后，第 $i$ 天的买入额度已经用掉，需要从堆中弹出。第 $k$ 天虽然卖出了，但后续如果有必要还是可以在这一天买入，只是整体看相当于这一天没操作而已，因此将第 $k$ 天的价格压入。

另一方面，对于 $p[k] - p[i]$ 的选择，后续可能会出现 $j$ 日卖出比 $k$ 日卖出更好的情况，即 $p[j] - p[i] > p[k] - p[i]$，此时应该反悔，将对应于第 $i$ 天买入的卖出时间从 $k$ 改为 $j$，总利润可以增加 $p[j] - p[k]$。

也就是说，我们直接在总利润中增加 $p[j] - p[k]$，就相当于撤销选择 $p[k] - p[i]$，改为 $p[j] - p[i]$ 的反悔操作。这样的话，只需要在堆中增加 $p[k]$ 即可。

根据上面的分析，$p[k]$ 压入了两次，其中一个对应的是正常的在第 $k$ 天买入、另一个对应的是反悔操作，将 $p[k] - p[i]$ 改为 $p[j] - p[i]$。

综上，基于反悔贪心思想的算法如下：

按照日期枚举每天的股价，过程中维护一个堆 pq 代表可以买入的日期对应的价格。假设当前枚举到 $p[i]$，此时 pq 中保存的是日期范围 $[0, i)$ 中尚未买入的日期对应的股价：

• 首先，不论 p[i] 与 pq.top() 的关系如何，都将 $p[i]$ 压入堆，代表第 $i$ 天买入的额度尚未使用，后续可以在这一天买入。
• 然后，假如 p[i] - pq.top() > 0，则将总利润增加 p[i] - pq.top()。将 pq 的堆顶弹出，因为其对应的日期刚刚买入了，同时将 $p[i]$ 压入堆，代表后续的反悔操作。

代码 (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> p(N);
    for(int i = 0; i < N; ++i)
        cin >> p[i];
    priority_queue<int, vector<int>, greater<int>> pq;
    int ans = 0;
    for(int i = 0; i < N; ++i)
    {
        pq.push(p[i]);
        if(!pq.empty() and p[i] > pq.top())
        {
            ans += p[i] - pq.top();
            pq.pop();
            pq.push(p[i]);
        }
    }
    cout << ans << endl;
}

---