Почему это работает
- Сделка со дня a до дня b приносит prices[b] − prices[a], а это сумма изменений цены по дням между ними. Поэтому одна длинная сделка на подъёме приносит ровно сумму его шагов вверх.
- Сделка поверх падения платит за это падение. Выбросить все отрицательные изменения и оставить все положительные — наибольшая сумма, какую они могут дать.
- Каждый подъём — сделка на один день, и такие сделки не пересекаются, поэтому эту сумму правда можно заработать, держа одну акцию за раз.
Сложность
Время O(n): один проход по дням. Память O(1): только profit и текущий rise.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗