找出最大的收益，通过进行至多两次交易（在列表中找到两个最大的不重叠的递增数列）。

Question

注意：没有交叉，第二次购买应晚于第一次销售。

给定一个股票在上一个交易日的报价流。假设它已经按时间排序。通过进行两次交易，找到你可以通过这只股票赚取的最大金额。买入和卖出算作一次交易。

例如：

time Price 
1 10 
2 11 
3 7 
4 15 
5 8 
6 17 
7 16 

答案是8+9，在3买入，在4卖出，再在5买入，在6卖出。

- user1647469

---

是我还是在7（4）买入，8（15）卖出，然后在9（5）买入，12（17）卖出可以获得更好的价值？ 8 + 12 = 20 - Samy Arous

@icfseth，我已经重新格式化了；现在可能更有意义了。 - Alex Brown

那我不能在3买入两次，然后在6卖出两次吗？ - Keith Randall

所以基本上你真正想要的是“在列表中找到两个最大的不重叠的增加”？ - Jerry Coffin

你是在寻求聪明的答案吗？对于每组4个独特点的组合，您可以计算在这些点上进行买入/卖出/买入/卖出所获得的利润。现在您知道在每种情况下可以赚多少钱，包括利润最大的情况。 - Drew Dormann

Answer 1

动态规划

d[i][j].b = 第i次交易后的收入，已经完成了j次交易，第j次交易只买入 d[i][j].s = 第i次交易后的收入，已经完成了j次交易，第j次交易买入并卖出 基础值 d[i][j].b = d[i][j].v = -inf; d[0][0].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)

- Herokiller