wqs 二分最初由王钦石在他的 2012 年国家集训队论文[1]中提出，而从 IOI 2016 的?Aliens?题目开始，这种方法开始逐步在竞赛圈中有了一定的地位。在国内我们一般称为「wqs 二分」，而在国外一般称为「Alien Trick」。

由于最初的论文讲解得比较简洁，因此我在学习 wqs 二分时还同时参考了[2]以及[3]两篇文章，其中[2]对于 wqs 二分能够解决的问题类型给出了明确的定义，[3]使用图解形象化地展示了 wqs 二分的本质。

本文将会结合力扣平台的题目?188. 买卖股票的最佳时机 IV?讲解 wqs 二分，同时这里抽象地给出 wqs 二分适用的题目类型：

给定??个物品，我们需要在其中 恰好选择? ?个，并且需要最大化收益。设对应的收益为? ?，那么需要满足 在最大化收益的前提下，每多选择一个物品，额外产生的收益是单调递减的，也就是? ?。同时，如果我们 对物品的选择数量没有限制，即? ?不存在，那么我们应当能够快速地计算出最大的收益，以及达到最大的收益需要选择的物品数量。

我们设恰好完成??笔交易时，能够获取的最大收益为??，那么

是成立的。我们可以这样想：我们每额外增加一笔交易?，那么这一笔交易一定不会比上一笔交易??产生的收益高，否则我们就可以交换这两笔交易，使得??更大，那么就与??是恰好完成??笔交易时的最大收益这个事实相矛盾了。

如果我们把??看成平面直角坐标系上的点，那么这些点就组成了一个上凸壳，如下图所示：

形象化地说，在最初的时候，随着??的增加，我们可以不断地通过买入卖出获得额外的正收益。但??到了一定的阈值之后，如果再强制进行交易，那么我们只能以高价买入，低价卖出，每多一笔交易，就会获得额外的负收益。因此，?对应的图像就是一个上凸壳，即随着??的增大，以??与??为端点的线段的斜率是单调递减的。

虽然我们并不知道??的值到底是多少（否则我们就可以直接返回正确答案了），但是我们知道??对应的图像的形状。wqs 二分的妙处就在于此，通过对斜率进行二分，求出??的值。

假设我们枚举了某斜率??，如上图所示，我们画出所有经过??并且斜率为??的直线。为了美观性，我们只画出了??的直线。我们发现，斜率为??的直线与上凸壳相切在了??的绿色点位置，根据上凸壳的性质，经过绿色点的这条直线与??轴的截距也是所有斜率为??的直线中最大的。

那么这个「截距」代表了什么？对于经过??而言，经过它并且斜率为??的直线在??轴上的截距是

而 k?恰好包含了??笔交易带来的收益，如果将这个收益减去??，那么就可以看做是每一笔交易都包含了??的手续费！当每一笔交易都包含了??的手续费时，如果规定了恰好进行??笔交易，那么最大的收益就是经过??并且斜率为??的直线在??轴上的截距。此时，?对应的截距是大，因此如果我们不限制进行的交易次数，那么最终得到的最大收益就是??。

这个子问题就是?714. 买卖股票的最佳时机含手续费，我们可以在??的时间内求出这个子问题的最大收益，并且可以顺便求出具体的交易次数。因此，如果我们选择了一个合适的斜率??，使得其与上凸壳相切在了某一个我们需要的??的位置（例如本题中给出的参数??），这样我们就可以在??的时间内直接求出不限制交易次数的最大收益，并且我们知道它实际上就是交易了??次。

这个神奇的方法怎么抽象地进行理解呢？我们可以这样想：随着斜率（手续费）??的增大，我们会趋向于进行更少次数的交易，在最大收益的前提下，交易的次数是具有单调性的，这也是由上凸壳保证的。例如在极端情况下?，我们不会进行任何一笔交易。因此我们就可以对??进行二分，如果找到了恰好进行??次交易的?，那么我们就得到了正确的答案。

然而上面的方法存在两个小问题：

• 第一个问题是很容易发现的：本题中我们限制的是最多进行??次交易，而不是恰好进行??次交易，那么上面的方法还适用吗？
• 我们是通过对二分来找出与题目中给定的??对应的??相切的斜率?。那么二分的上下界如何确定？并且这个斜率??一定存在吗？

对于第一个问题，我们分两种情况进行讨论：

• 如果 k,gk?所在的位置是上凸壳的左半部分（即斜率大于等于??的部分），那么我们就可以使用上面的方法得到答案，这是因为最优的答案一定是进行??次交易的；
• 如果 k,gk?所在的位置是上凸壳的右半部分（即斜率小于??的部分），那么我们通过二分是没有办法找到斜率??并且计算出对应的??的。具体的做法可以在第二个问题中得到解释，也就是我们可以规定二分查找的上下界。

对于第二个问题，我们规定二分查找的下界为 1?，这样当??所在的位置是上凸壳的右半部分时，二分查找就会失败。二分查找的上界可以设定得宽松一些，由于每一条线段的斜率都不会超过数组??中给定价格的最大值，因此可以将上界设定为这个最大值。如果二分查找失败，那么说明最大收益对应的交易次数是严格小于题目中给定的??的，这就说明交易次数的限制并不是瓶颈，而价格才是，因此我们可以直接使用?122. 买卖股票的最佳时机 II?中的贪心方法计算出最终答案。

不过可能会有另外一种情况导致二分查找失败，即如果上凸壳上有若干连续的且斜率相等的线段，例如下图所示，那么在查找到该斜率 c?时，我们只会计算出一个对应的??值（例如图中绿色的点），然而实际上是有不止一个??值是满足要求的 （例如图中红色的点），这些点对应的截距都是最大值，那么如果题目中给定的??对应的是红色的点，那么二分查找就会失败。

对于这种情况，我们可以在求解子问题时，尽可能地多进行交易，求解出最大的那个??值。从本质上来说，红色的点与绿色的点之间实际上只是相差了若干笔收益为??的交易而已，因此它们之间都是可以互相转换的。

最后需要注意的是：我们求解子问题时得到的收益是 gk-k.c，所以别忘了将这个收益加上??才会得到最终的答案。

?
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }

        int n = prices.size();
        // 二分查找的上下界
        int left = 1, right = *max_element(prices.begin(), prices.end());
        // 存储答案，如果值为 -1 表示二分查找失败
        int ans = -1;
        while (left <= right) {
            // 二分得到当前的斜率（手续费）
            int c = (left + right) / 2;

            // 使用与 714 题相同的动态规划方法求解出最大收益以及对应的交易次数
            int buyCount = 0, sellCount = 0;
            int buy = -prices[0], sell = 0;

            for (int i = 1; i < n; ++i) {
                if (sell - prices[i] >= buy) {
                    buy = sell - prices[i];
                    buyCount = sellCount;
                }
                if (buy + prices[i] - c >= sell) {
                    sell = buy + prices[i] - c;
                    sellCount = buyCount + 1;
                }
            }

            // 如果交易次数大于等于 k，那么可以更新答案
            // 这里即使交易次数严格大于 k，更新答案也没有关系，因为总能二分到等于 k 的
            if (sellCount >= k) {
                // 别忘了加上 kc
                ans = sell + k * c;
                left = c + 1;
            }
            else {
                right = c - 1;
            }
        }

        // 如果二分查找失败，说明交易次数的限制不是瓶颈
        // 可以看作交易次数无限，直接使用贪心方法得到答案
        if (ans == -1) {
            ans = 0;
            for (int i = 1; i < n; ++i) {
                ans += max(prices[i] - prices[i - 1], 0);
            }
        }

        return ans;
    }
};

?