c++ - 查找最多进行 2 次交易可以赚到的最大资金（在列表中查找两个最大的非重叠增量）

Question

注意：没有重叠，第二次买入应该晚于第一次卖出。

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

例子：

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

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

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)