Найдите максимальное количество денег, которое вы можете сделать, совершив не более 2 транзакций (найдите два самых больших непересекающихся увеличения в списке)
Примечание: нет перекрытия, вторая покупка должна быть позже первой продажи.
Приведен поток котировок на акции с последнего торгового дня. Предположим, его уже раз отсортировано. Найдите максимальную сумму денег, которую вы могли бы заработать на этой акции, совершив 2 транзакции. Покупка и продажа учитываются как одна транзакция.
Пример:
time Price
1 10
2 11
3 7
4 15
5 8
6 17
7 16
ответ 8 + 9 купить на 3, продать на 4, купить на 5, продать на 6.
Решение
Динамическое программирование
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) в этом случае
Другие решения
Других решений пока нет …