首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >通过最多两笔交易找出你能赚到的最多的钱(在列表中找出两个最大的不重叠的增长)

通过最多两笔交易找出你能赚到的最多的钱(在列表中找出两个最大的不重叠的增长)
EN

Stack Overflow用户
提问于 2012-09-05 06:21:18
回答 1查看 897关注 0票数 3

注:无重叠,第二次买入应晚于第一次卖出。

给定上一个交易日股票的一系列报价。假设已经对时间进行了排序。通过两次交易,找出你在这只股票上能赚到的最大金额。买入和卖出被算作一笔交易。

示例:

代码语言:javascript
代码运行次数:0
运行
复制
time Price 
1 10 
2 11 
3 7 
4 15 
5 8 
6 17 
7 16 

答案是8+9在3买,在4卖,在5买,在6卖。

EN

回答 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

代码语言:javascript
代码运行次数:0
运行
复制
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

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/12272131

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档