Проблема LeetCode 121: лучшее время для покупки и продажи акций
Вам дан массив цен, где цены[i] — это цена данной акции на i-й день.
Вы хотите максимизировать свою прибыль, выбрав один день для покупки одной акции и выбрав другой день в будущем для продажи этой акции.
Верните максимальную прибыль, которую вы можете получить от этой сделки. Если вы не можете получить прибыль, верните 0.
Пример:
Входные данные: цены = [7,1,5,3,6,4] Выход: 5 Пояснение: Покупайте в день 2 (цена = 1) и продавайте в день 5 (цена = 6), прибыль = 6-1 = 5. Обратите внимание, что покупка во второй день и продажа в первый день не разрешены, поскольку вы должны купить, прежде чем продавать.
def maxProfit(self, prices: List[int]) -> int:
the tests
tempProfit = 0
for z in range(0, len(prices)+1):
####if (prices[z] < prices[z+1]):###
for x in range(z, len(prices)):
if (prices[x] - prices[z] > tempProfit):
tempProfit = prices[x]-prices[z]
return(tempProfit)
Подход, который я попробовал, представляет собой своего рода «грубое принуждение» к получению максимальной прибыли за все дни и сохранению максимальной прибыли. он прошел большинство тестов, кроме 1 — теста с очень длинным нисходящим значением. [10000,9999,9998,9997.......0], что произошло из-за длительного времени выполнения (из-за грубого принуждения) Чтобы решить эту проблему, я пытаюсь добавить оператор if, который позволит избежать прохождения второго цикла for, если цена[z] > цена[z+1]. Это не работает, потому что длина списка выходит за пределы последней итерации. Как я могу реализовать свою логику в этом цикле for, не выходя за пределы длины списка?
Ответы 1
Для каждого дня при покупке акций лучшим временем для продажи является день с самой высокой ценой после текущего индекса в массиве. Таким образом, вы можете выполнить итерацию в обратном порядке и сохранить текущую самую большую цену, встречавшуюся на данный момент для линейного решения.
def maxProfit(self, prices: List[int]) -> int:
max_price = max_diff = 0
for price in reversed(prices):
max_diff = max(max_diff, max_price - price)
max_price = max(max_price, price)
return max_diff
Аналогичная логика может быть применена для итерации вперед и поддержания минимума.