В своем постоянном стремлении отточить свои навыки LeetCode я решил проблему «Лучшее время для покупки и продажи акций II». Эта задача является продолжением классической задачи «Лучшее время для покупки и продажи акций II» (LeetCode 121), но с существенным отличием: *вы можете выполнять несколько транзакций для максимизации прибыли.
*

Визуальный подход

Прежде чем углубиться в код, мне было невероятно полезно визуализировать проблему на доске. Это позволило мне разбить проблему на более мелкие и более выполнимые шаги.

Жадный подход

Учитывая возможность совершать неограниченное количество транзакций, жадный подход казался многообещающим. Основная идея проста: всякий раз, когда цена акции увеличивается по сравнению с предыдущим днем, мы рассматриваем это как потенциальную возможность получения прибыли. Сложив все эти ценовые разницы, мы фактически рассчитываем максимальную прибыль.

Реализация Python

Вот код Python, реализующий эту жадную стратегию:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit =prices[i] - prices[i-1]

        return profit

Реализация JavaScript

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var profit = 0;
    for (var i = 1; i  prices[i-1])
    {
        profit  = Number(prices[i] - prices[i-1])
    }
    }

    return profit
};

Временная и пространственная сложность

• Временная сложность этого подхода равна O(N), где N = длина массива.
• Пространственная сложность равна N(1), поскольку мы сравниваем на месте.