🧑‍🎓 Решение задачи «Лучшее время для покупки и продажи акций»

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

Решение: Предлагается решить задачу с помощью двух указателей. Сначала иницаилизируем левый и правый указатели для покупки и продажи соответственно. Также инициализируем нулём нашу прибыль (max_profit).

Далее мы проходим по массиву цен, используя цикл while, пока right (день продажи) меньше длины массива. На каждом шаге вычисляем текущую прибыль от продажи акции в день right, купленной в день left.

Если prices[left] < prices[right], это означает, что покупка акции в день left и продажа в день right приводит к положительной прибыли. В этом случае обновляется max_profit, если currentProfit больше текущего значения max_profit. Если цена покупки больше или равна цене продажи (prices[left] >= prices[right]), это означает, что продолжать держать текущую акцию не имеет смысла, и следует рассмотреть акцию в день right как новую точку покупки. Таким образом, left обновляется до right.

По окончании цикла возвращается max_profit. Если сделок, приводящих к прибыли, не было, функция вернёт 0. Сложность алгоритма O(n).

▶️Код:

def maxProfit(prices):
    left = 0 #Покупка
    right = 1 #Продажа
    max_profit = 0
    while right < len(prices):
        currentProfit = prices[right] - prices[left] 
        if prices[left] < prices[right]:
            max_profit =max(currentProfit,max_profit)
        else:
            left = right
        right += 1
    return max_profit