Best Time to Buy and Sell Stock

Тебе известны цены одной акции в течение нескольких дней — по одной цене за день. Ты можешь купить одну акцию в какой-то день и продать её в более поздний день. Прибыль — это цена продажи минус цена покупки, и ты хочешь получить максимально возможную прибыль. Если каждая сделка принесла бы убыток, просто не торгуй и получи 0.

Возьмём цены [7, 2, 5, 9, 1, 4]. Покупка за 2 в день 1 и продажа за 9 в день 3 принесёт 7, и никакая другая пара дней не даст больше. Покупка за 1 в день 4 кажется заманчивой, потому что это самый дешёвый день, но в единственный более поздний день акция продаётся за 4, поэтому эта сделка принесёт всего 3.

Проверить каждую пару дней можно, но для длинных списков цен это слишком медленно. Вместо этого можно пройти по дням всего один раз. Если ты продаёшь сегодня, лучше всего было купить в самый дешёвый из уже прошедших дней, поэтому по ходу дела сохраняй эту минимальную цену. Лучшая прибыль за сегодня — это сегодняшняя цена минус минимальная цена, а ответ — наибольшее из этих значений.

Напиши функцию с именем maxProfit, которая получает список целых чисел prices, где prices[i] — цена акции в день i, и возвращает наибольшую прибыль, которую можно получить, купив акцию в один день и продав её в более поздний день. Если ни одна сделка не приносит прибыли, верни 0.

Ограничения: 1 ≤ prices.length ≤ 10^5, 0 ≤ prices[i] ≤ 10^4.