Код Junior Жадные обновлено
Лучшая сделка
Условие
Массив цен по дням. Максимальная прибыль от одной покупки и одной последующей продажи. Если прибыли нет - 0.
Примеры
maxProfit([7, 1, 5, 3, 6, 4]) // 5
maxProfit([7, 6, 4, 3, 1]) // 0
maxProfit([]) // 0
Как подойти
Один проход: минимум слева плюс лучшая разница. Вложенный перебор пар дал бы O(n²). Follow-up - неограниченное число сделок решается суммой всех положительных разностей соседей.
Подсказки: 1
- Веди минимальную цену слева от текущего дня.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.