Задача с собеседования в Zoox

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

Пример 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Объяснение: Покупаете акцию во 2-й день (цена = 1) и продаёте в 5-й (цена = 6). Прибыль: 6 - 1 = 5. Обратите внимание, что покупка во 2-й день и продажа в 1-й невозможна, так как вы должны сначала купить, а потом продать!

Пример 2:
Input: prices = [7,6,4,3,1]
Output: 0
Объяснение: В этом случае сделок не совершается (нет выгодных условий), и максимальная прибыль равно 0.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Для получения максимальной прибыли - покупаем на минимуме и продаём на максимуме. Заводим две переменные: min_price (находим самую выгодную цену) и max_profit (ищем наибольшую разницу между минимумом и текущей стоимостью акции).
Осуществляем проход по массиву и сравниваем минимальную цену (вначале она равняется первому эл-ту массива) с текущей. Если текущая меньше минимальной, обновляем значение минимума. Последний найденный минимум - цена, по которой мы купим акцию. Далее, в независимости от того, выполнилось ли условие для обновления минимума, проверяем: будет ли максимальной прибыль от продажи акции в текущий день. Сравниваем ранее найденное значение max_profit с прибылью, которую получим от продажи акции "сегодня". После окончания работы цикла выводим max_profit с последним вписанным в переменную значением.
Задача помечена тегом "Dynamic Programming", подход использован в решении: мы храним две переменные (min_price, max_profit) и используем их найденные значения для вычисления следующих.

Сложность
O(n) - по времени
O(1) - по памяти

Код
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0

min_price = prices[0]
max_profit = 0

for price in prices:
if price < min_price:
min_price = price

max_profit = max(max_profit, price - min_price)

return max_profit

@algoses