Почему это работает
- buy[j] и sell[j] — состояния j-й сделки: держим её акцию и закончили с ней. j-я покупка начинается от sell[j − 1], денег после j − 1 сделок, поэтому сделки идут одна за другой и не пересекаются.
- k ограничивает число сделок, потому что sell[k + 1] нет. При трёх подъёмах и k = 2 таблица выбирает: пересидеть падение 6 → 4 стоит 2, бросить самый маленький подъём 2 → 5 стоило бы 3, поэтому 1 → 9 и 2 → 5 (11) лучше, чем 1 → 6 и 4 → 9 (10).
- Каждый день состояние сохраняет вчерашнее значение или приходит из предыдущего по сегодняшней цене, поэтому sell[k] — лучшее среди всех способов расставить не больше k сделок.
Сложность
Время O(n·k): в каждый из n дней внутренний цикл обновляет по два числа для каждой из k сделок. Память O(k): два массива, которые каждый день перезаписываются на месте.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗