Почему это работает
- Четыре состояния описывают любой момент: держим первую акцию, первая продана, держим вторую, вторая продана. Каждый день состояние либо остаётся прежним, либо в него приходят из предыдущего по сегодняшней цене, поэтому его число — лучшее среди всех историй, которые в нём кончаются.
- buy2 = sell1 − p оплачивает вторую акцию из прибыли первой сделки. Так 2 → 6 и 3 → 9 (10) обгоняют одну сделку 2 → 9 (7): из падения с 6 до 3 мы выходим, а не пересиживаем его.
- Состояния обновляются одно за другим в тот же день, так что следующее может прочитать значение, записанное сегодня. Это лишь добавляет покупку и продажу по одной цене, которые дают 0, поэтому лишняя прибыль не появляется.
Сложность
Время O(n): один проход по дням, на каждом четыре обновления. Память O(1): четыре числа при любом числе дней.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗