Best Time to Buy and Sell Stock IV
My SubmissionsQuestion Solution
Total Accepted: 14439 Total Submissions: 75667 Difficulty: Hard
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.
Hide Tags
Hide Similar Problems
(M) Best Time to Buy and Sell Stock (M) Best Time to Buy and Sell Stock II (H) Best Time to Buy and Sell Stock III
难度确实比较大，第一次边做边写。
首先是想想前三题跟这一道题的关系：
假设在整个数组中，有 n 个上升的区段（不是 n 个上升的天数，一个上升区段可能包括好几天），以及 m 个上升天数
-- 如果 k=1，那实际上就是第一题，一次交易，策略是跟踪最低价，累计最大的利润差；
-- 如果 k=n，那实际上就是第二题， n 次交易，策略是拿到所有的上升区段，获取最大利润；
-- 如果 k=2，那实际上就是第三题，两次交易，策略是转化为第一题，分别比较以某一天为界限的
（前半程一次交易最大利润 ）与 （后半程一次交易最大利润） 之和 的最大值。
所以，对于 k 为 任意一个值，也就是交易任意次的情况，首先可以按照 k 和 n 的关系分为两种情形：
-- 如果 k >=n ，那么实际上就是第二题，拿到所有的上升区间即可。
-- 如果 k < n，则可以有两种思路：
-- 将 k 次交易的最大利润分为 前半程 后半程，并依次递归地切分下去，直到切分到一次为止，复杂度 n^(lgk)，太高。
-- 将 n 个上升区间进行合并，看看合并/拆分分别获取的利润如何变化，从中推算可以获得的最大利润；
其复杂度取决于实际情况，很难一句话概括。
从基本的关系来看，合并两个上升区间，大致有上面六种可能。
第一种是后一个上升区间起点终点都比现在的高。此时 合并 和 拆分 相比，合并可以比单独取某一个获得更多利润，
并且拆分可以获得额外的一部分利润（重叠的部分），或者，如讨论区的某个帖子里说的，前一个波峰减去后一个波谷。
第二种是前后连续，这实际上跟第一种是一样的情况，只不过重复的部分为 0 而已，所以可以并入第一种情况。
第三种情况是后一个上升区间被第一个包含。此时类似第一个，拆分可以获得额外的重叠部分，
但跟第一种情况比起来，合并后的结果并不会比单独取第一个更大。
第四种情况跟第三种正好倒过来，后一个包含了前一个的上升区间，此时合并不会扩大，拆分享受重叠部分。
第五种情况是后一个上升区间起点更低，但终点并未超过前一个，此时合并的结果比任何一个单一的上升区间都更小，
所以无论可以买卖多少次，都不可能是取合并的结果，也就是说，此时，完全不必考虑合并的可能性。
第六种类似第五种，不同的是两个上升区间完全不重叠，此时同样不需要考虑合并的可能性，因为合并的结果是亏的。
所以，综合来看，第一/二是一个情况，如果次数允许，尽可能分开，次数不允许合并也不错；
第三/四的情况是，次数允许的话，也尽量分开，次数不允许，不必考虑合并，选大的即可；
最后两种情况则无论如何都不用考虑合并，选大的即可。
基于这三类情况再考虑延伸的情况，
前两种实际上合并也就变成了一个区间，所以可以继续套用上面的分析；
中间两种则要看已知的两者关系，以及后面叠加的上升区间与它们的关系：
如果两者是第三种，前大后小，但后续的上升区间跟第二个上升区间可以叠加，且叠加之后新终点超过第一段的终点，
则应该先考虑后面的叠加，然后回头再与第一个叠加，这实际上是变成了嵌套的第一种情况。
如果后续形不成叠加，那么套用其他情况，套用完毕之后再看跟第一个的关系来定。
如果两者是第四种，前小后大，后面能否形成叠加对于较小的第一个上升区段已经不重要了，单独考虑取舍它就好了。
后两种情况既然不存在叠加的必要，实际上也就只需要看第二段跟后续的关系，前一段可以视为单独取舍了。
因此，我们可以得到大致的处理思路：
1. 从前向后扫描数组，将一次“波谷--波峰”的上升区间作为一个基本的处理单元；
2. 既然要比较，就要保存前面的“波谷--波峰”上升区间，考虑到中间两种的延伸有可能向前回头去合并，最好用栈；
3. 如果后一段的起点比前一段的起点更低（第四/五/六种情况），
就意味后一段跟前一段（可能是由之前的多次合并形成的）不再有 dependence 了，前一段可以从栈里拿掉。
4. 如果可以合并，就进行合并之后再继续，同时因为栈里有之前的结果，也就可以进行回溯；
合并之后，新的起点终点就要按照时间来合并，以便后续进行管理；
4. 扫描与保存上升区段的同时，也要记录最大利润的变化，以便计算 k 次交易可以获得的最大可能利润。
合并与否，对于最终利润的影响，实际上就是要不要多算一次两段重复的部分，
遇到一个（可以合并的）新上升区段时，最大利润可能为，a）两段之和（不合并）；b）两段只和 - 重叠部分（合并）。
要记录这两种情况，可以有不同的方法来保存已经扫描过的部分：
例如，保存 1. 第一段的单独利润；2. 第二段的单独利润；3. 重叠部分的利润；
或者，保存 1. 第一段的单独利润；2. 重叠部分的利润；3. 合并后的单独利润；
第二种实际上合并后的单独利润就是当前起点终点的利润差，也有利于继续合并，所以选择后者。
这样，如果只能交易一次，就取 1, 2，以及合并后的起点终点利润差 三者中的最大值，
而如果可以交易两次，则可以通过合并后的起点终点利润差 + 重叠部分的利润来获得最大收益。
延伸出去，对于更多次交易的情况，
可以持续选择所有保存的未选中的最大收益，无论它是单次利润还是重复部分（重叠实际上也就意味着拆分嘛）。
因此最适合的数据结构是--堆。
基于这些形成了 merge 的解法：（思路源于这个帖子，但作者没从 merge 的角度解释，只说 key是前一个波峰减后一个波谷）
在 stack 里存入更新过的或者是新的上升段，边往后扫描边合并，并计算重叠利润部分，全部完成之后从堆里构建结果。
最终的结果是 12 ms（后来加上对 k >=n 的单独处理，减到 8 ms），性能还不错。
。。。这个做法隐约似乎可以算作是一种回溯么？
当然题目本身期待的解法是 DP，所以还是去学习了一下 DP 的思路。
可以找到很多 DP 的讨论，不一而同，比较常见的有：
（1）local / global 的做法，分别维护两个数组，表示 till/cross day i，直到现在还看得有点晕。
（2）sell/hold的做法，分别维护 sell/hold 两个数组，交替计算，还挺清楚的：
算法核心是（在第i天第j次持有的盈亏最大是取两个的较大值）： cur = prices[i];另外有一个帖子对这个问题的 DP 讲得比较本质： hold[j] = max(hold[j],sell[j-1] - cur); //继续持有 sell[j] = max(sell[j],hold[j] + cur); //在第j-1次卖出后，第i天重新买入
f[i][j] 代表第 i 天为止交易 k 次获得的最大收益，
那么将问题分解为前 x 天交易 k-1 次，第 x+1 天至第 i 天交易一次两个子问题，动态方程：
f[i][j] = max(f[x][j - 1] + profit(x + 1, i))受这个描述的启发，仔细琢磨了一下讨论区的另一个帖子，理出了一个 DP 的思路：
将交易 k 次的最大利润，分解为交易一次又一次的累积过程，新一轮即多一次交易，其利润计算，是基于上一轮的累积结果的。
具体而言：
第一次交易，一边扫描价格数组，以便计算到扫描所及的位置为止，可以获得的最大利润，用价格数组同样的下标填入利润数组；
扫描完成，最后一个格子里存的，就是如果只做一次交易，可以获得的最大利润了。
同时，利润数组里记录了截至每一天，可以获得的最大利润，这个数组，可以看作是“下一次交易的本金”。
到了第二次扫描的时候，不但要看买卖获取利润的情况，还要考虑手头的“本金”，来合计最大的利润。
因此，实际上可以将利润视为两个部分组成： （两者之和，即时总体利润)
基数，也就是本金，来自之前的积累；
变数，也就是本轮中买卖所得。变数部分 = 当天的价格 — 买入点的价钱。
第二轮累积完成，利润数组就成了第三轮的本金，继续累积，直到完成 k 轮。
而至于买入点，参考第一题的情况可以知道，如果遇到价格新低，就可以作为新的买入点了。
所以整个 DP 的过程就是：
-- 检查是否有新低，有的话，更新买入点的信息，记录买入点的价格，以及买入点当天的基数（本金）。
-- 每天计算变数部分的利润，即当天价格跟买入点价格的差价，
并加上基数部分（不是当天的，是买入点的基数）求和，再跟当天的基数比，取大的作为本轮的累积结果（下一轮的本金）。
-- 如此往复，共计 k 轮，结束之后，利润数组的末尾数字，就是 k 次交易可以获得的最大利润啦。
基于这个过程写了一个 DP ，不断更新一维数组里的累积利润，直到完成 k 次，复杂度是 O(nk)，结果是 8 ms.
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int sz=prices.size();
if(2>sz)
return 0;
//for cases k bigger than total amount of increasing segments
int idx=0, seg=0, sum=0;
while(idx<sz-1)
{
while(idx<sz-1 && prices[idx]<prices[idx+1])
idx++, sum+=prices[idx]-prices[idx-1];
seg++;
while(idx<sz-1 && prices[idx]>=prices[idx+1])
idx++;
}
if(k>=seg)
return sum;
//other cases
//return maxProfit_dp(k, prices);
return maxProfit_merge(k, prices);
}
//-------------------------------------- DP Solution --------------------------------------
int maxProfit_dp(int k, vector<int>& prices) {
int sz=prices.size();
int idxBuy=0; //buy at some a day
int profitBase=0; //base part of profit, accumlated previously
int profitOfst=0; //dynamic part of profit with new purchase
int profits[sz]; //buffer to accumulative profits
for(int ii=0; ii<sz; ++ii)
profits[ii] = 0;
for(int kk=0; kk<k; ++kk) //will try accumulate with 1...k transactions
{
idxBuy = 0; //start from first day
profitBase = profits[0];
profitOfst = profits[0] - prices[0];
for(int ii=1; ii<sz; ++ii)
{
if(profitOfst < (profits[ii] - prices[ii])) //new lowest price to buy, buy it
{
idxBuy = ii;
profitBase = profits[ii]; //update base part of profit
profitOfst = profits[ii] - prices[ii]; //update dynamic part of profit
}
profits[ii] = max(profits[ii-1], //if don't sale today
profitBase + (prices[ii]-prices[idxBuy])); //if sale it today
}
}
return profits[sz-1];
}
//-------------------------------------- Stack solution --------------------------------------
int maxProfit_merge(int k, vector<int>& prices) {
int sz=prices.size();
int ftc=0, pkc=0; //current foot/peak
int ftp=0, pkp=0; //previous foot/peak
priority_queue<int> pf; //heap to store profits
stack<pair<int, int>> seg; //increasing segments
while(pkc<sz)
{
while(ftc<sz-1 && prices[ftc]>=prices[ftc+1])
ftc++; //get new foot
pkc = ftc;
while(pkc<sz-1 && prices[pkc]<=prices[pkc+1])
pkc++; //get new peak
while(seg.size()
&& (prices[ftc]<prices[seg.top().first] //no impact future segments
|| pkc==sz-1)) //or all prices are scanned
{
pf.push(prices[seg.top().second]-prices[seg.top().first]);
seg.pop(); //this pair is done, pop it.
}
//merge-able cases
while(seg.size()
&& prices[pkc]>prices[seg.top().second] //new peak is higher
&& prices[ftc]>=prices[seg.top().first]) //new foot is higher
{
pf.push(prices[seg.top().second]-prices[ftc]); //push overlap profit
ftc = seg.top().first; //merge with previous segment
seg.pop(); //keep checking possible previous
}
if(pkc<sz && ftc<pkc) //don't insert if hits the end prices
seg.push({ftc, pkc}), //push merged/new segment into stack
ftc = pkc; //move to latest position
else
break;//pkc++;
}
int rst=0;
while((k--)&&pf.size())
rst+=pf.top(), pf.pop(); //build result from heap
return rst;
}
};
8 ms, 8 ms.
No comments:
Post a Comment