通过最多两笔交易找出你能赚到的最多的钱(在列表中找出两个最大的不重叠的增长)
通过最多两笔交易找出你能赚到的最多的钱(在列表中找出两个最大的不重叠的增长)
提问于 2012-09-05 06:21:18
注:无重叠，第二次买入应晚于第一次卖出。
给定上一个交易日股票的一系列报价。假设已经对时间进行了排序。通过两次交易，找出你在这只股票上能赚到的最大金额。买入和卖出被算作一笔交易。
示例：
time Price
1 10
2 11
3 7
4 15
5 8
6 17
7 16 答案是8+9在3买，在4卖，在5买，在6卖。
回答 1
Stack Overflow用户
发布于 2012-09-05 12:23:21
动态编程
di.b =第i次之后的收入，已经进行了j次交易，第j次交易仅购买di.s =第i次之后的收入，已经进行了j次交易，第j次交易买卖基础di.b = di.v = -inf；d.s = 0；
在这种特殊情况下，j仅为1-2
d[i][j].b = max(d[i-1][j-1].s - price[i], d[i-1][j].b)
d[i][j].s = max(d[i-1][j].b + price[i], d[i-1][j].s)像这样的东西
O(n*k)其中k-事务的数量，因此在这种情况下为O(n
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12272131
复制相关文章
相似问题
腾讯云开发者
