Лучшее время для покупки и продажи акций. Решение через восходящие тренды

Если внимательно посмотреть на график, то можно заметить, что максимальная возможная прибыль складывается из сумм разниц стоимости акции между днями на восходящих трендах.

Это значит, что мы можем сильно упростить решение и не запоминать локальные минимумы и максимумы. Нам достаточно найти все возрастающие отрезки на графике и проссумировать разницу между ценой акции в эти дни.

Посмотреть реализацию

🅾️ Оценка сложности

n - количество элементов в массиве.

По времени
Сложность по времени O(n), так как мы итерируемся по всем элементам массива.

По памяти
Сложность по памяти O(1), так как мы не создаем дополнительных переменных.

#arrays #medium