Решение задачи

Алгоритм решения задачи:

Нам дан массив [7, 1, 5, 3, 6, 4]

Если мы нанесем числа данного массива на график, то получим:

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

Мы можем поддерживать две переменные - минимальную цену и максимальную прибыль, соответствующие наименьшей долине, и максимальную прибыль (максимальную разницу между продажной ценой и минимальной ценой), полученную на данный момент соответственно.

Временная сложность: O(n). Нужен только один проход.

Пространственная сложность: O(1). Используются только две переменные.