3

注: 重複はありません。2 回目の購入は、最初の販売よりも遅くする必要があります。

最後の取引日からの株式の相場のストリームが与えられます。すでに時間がソートされていると仮定します。この株で 2 回の取引を行って得られた最大の金額を求めてください。売買は1回の取引としてカウントされます。

例：

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

答えは 8 + 9 で、3 で買い、4 で売り、5 で買い、6 で売る。

4

1 に答える 1

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)

于 2012-09-05T04:23:21.477 に答える