LeetCode Best Time to Buy and Sell Stock IV(k不重叠最大子段和)线性解法

题目描述

Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Credits: Special thanks to @Freezen for adding this problem and creating all test cases.

分析

在https://leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack看到，但没说清理由。今天在地铁上把前后都想清楚了，特此记录。

令价格向量为，天数为。问题要求给出个买入时刻和个卖出时刻，满足，使最大。

另外，这个问题等价于求出的差分向量的k不重叠最大子段和。下面给出一个线性算法，但没有用到。

不失一般性，可以要求每个为局部极小值，满足或，且；每个为局部极大值，满足，且或。若最优方案不满足这个条件，可以调整和以满足这个条件，仍保持最优性。

先线性扫描，得到所有(上文定义的)局部极小和极大值。把它们按指标(向量中位置)顺序排序，指标最小的若是局部极大值则舍弃，指标最大的若是局部极小值也舍弃。余下的序列满足局部极小和局部极大交替出现，且局部极小值先出现。设该序列为，长度为，把和配对，称为一个pv对(valley和peak)，性质是。

下面研究一下最佳方案的性质。

对于一个pv对，第天会买入或不作操作，不会卖出；第天会卖出或不作操作，不会买入。一个pv对并非捆绑的，即第天买入不意味着在第天卖出，可以在之后的某个pv对卖出。最佳买入时刻和卖出时刻(不超过对)一定在这个指标里。

设的利益为。我们设法变换这个pv对，得到若干不超过个新的pv对(可能会有，也不再保证)，使得按利益从大到小选取不超过个(因为可能有负收益)，其利益和等于题目所求的最大收益。变换过程中的所有pv对称为候选pv对。

考虑相邻两个候选pv对：、，四个指标对应四个元素：。若4个数互不相等，则用0~3表示相对大小，有6种情形：

  • 0123。由于，不应在第天卖出后在第天买入。若两相邻候选pv对满足此情形，可保证1处不会卖出，2处不会买入，因此可以把这两个pv对替换成一个pv对：，称该操作为合并。合并操作使pv对数目减少一，可以看作01的peak改变了，但其valley不变。

  • 0213。可以把这两个pv对变换成：，注意第二个pv对的p和v顺序颠倒了，称这个操作为重组。重组后pv对数目不变，收益和守恒，但重组后两pv对的收益较大值增大了。若两个pv对只能取一个，则应取收益较大的那个，因此重组是有利的。重组操作的valley也不变。枚举四个点可能取的操作，可以发现重组不会使最佳方案变差。

  • 2301。特征是前一个pv对的valley小于后一个pv对的valley。考虑最佳方案可能在四个点取的操作：

    • 只有一个买入点。应放在0处。
    • 只有一个卖出点。应放在3处。
    • 一个卖出点后跟一个买入点。应放在3处和0处。
    • 一个买入点后跟一个卖出点。两种可能：2处和3处，或0处和1处。
    • 其他。分析方法和上面类似。

    另外在这种情形下，23和之后的某个pv对合并或重组并非最优。合并或重组满足valley不变，即使01与之后的pv对合并或重组了，这两个pv对也不会再满足合并或重组条件。

  • 1203。和上一种情形特征相同，结论相同。

  • 1302。和上一种情形特征相同，结论相同。

  • 0312。合并或重组并非最优。但12可能会与之后的pv对合并或重组，回到0123或0213两种情形，从而满足合并或重组条件。

4个数若有相等，亦可归入上述6种情形。

注意合并和重组都满足valley不变，且有益的合并或重组会使peak增大，使得更容易满足完成未来的合并或重组条件。这说明只要合并或重组有益，就应贪心进行。

另外“一旦不满足合并或重组条件，则之后也不再满足”。我们可以用栈维护候选pv对，表示可能会和未来的某个pv对重组或合并。从栈底到栈顶的各pv对满足三个单调性：一是位置单调递增，二是相邻两pv对满足，三是。

栈初始为空，另外维护一个队列。按指标的递增顺序扫描各候选pv对，若栈顶与扫描到的pv对满足2301、1203或1302(特征是前一个pv对的valley小于后一个pv对的valley)，则应弹出栈顶，插入到队列中。弹出若干pv对直到满足不再出现这三种情形。

假如栈非空且栈顶与扫描到的pv对满足0123或0213，则应根据之前的说明进行合并或重组，弹出的pv对都应插入到队列里。弹出若干pv对直到满足不再出现这两种情形。然后把扫描到的pv对压栈。

所有pv对扫描完后，栈中相邻元素满足0312，全部弹出并插入到队列里。

队列中所有元素即为变换后的候选pv对。按利益从大到小排序，选取不超过个利益非负的，其利益和等于题目所求的最大收益。这一步可以用quick select(C++的nth_element)在线性时间内计算：选取利益第大的，则排在它前面的元素收益都不小于它。

实现

代码见https://github.com/MaskRay/LeetCode/blob/master/best-time-to-buy-and-sell-stock-iv.cc。

另外此题也在http://codeforces.com/problemset/problem/391/F3出现。网路上找到的实现都是基于差分向量的，较复杂。