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

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

Возьмем для примера следующий массив цен в долларах [20, 10, 15, 5, 10, 20, 10] и представим его в виде графика.

Теперь на графике хорошо видно, что нам нужно сделать две покупки и две продажи:

- купить акцию на второй день за 10 и продать на третий день за 15
- купить акцию на четвертый день за 5 и продать на шестой день за 20

В итоге мы сможем получить максимальную прибыль и заработать $20.

Таким образом решение задачи сводится к тому, что нужно проходить весь массив и искать в нем локальные минимумы и локальные максимумы. Как только мы встречаем минимум, мы запоминаем цену в этот день. Как только встречаем максимум, мы вычисляем разницу между последним минимумом и максимальной ценой и прибавляем ее к нашему общему заработку.

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


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

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

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

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

#arrays #medium