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

Задача с собеседования в 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