714. Best Time to Buy and Sell Stock with Transaction Fee

Задача

Даны массив цен prices и комиссия fee. Максимизируйте прибыль при неограниченных сделках с уплатой комиссии за каждую.

Примеры

Пример 1

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

Пояснение

Купить по 1, продать по 8; купить по 4, продать по 9. Прибыль ((8-1)-2) + ((9-4)-2) = 8.

Пример 2

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

Решение

Решение

// Time Complexity: O(n) - проходим по массиру один раз
// Space Complexity: O(1) - используем только две переменные
 
function maxProfit(prices, fee) {
    if (prices.length === 0) return 0;
 
    // прибыль, когда держите акцию (обычно отрицательная)
    let hold = -prices[0]; // держим акцию (купили в день 0)
    // прибыль, когда не держите акцию (положительная после продажи)
    let notHold = 0; // не держим акцию
 
    for (let i = 1; i < prices.length; i++) {
        // Какая максимальная прибыль, если на конец дня i у меня ЕСТЬ акция?
        const newHold = Math.max(hold, notHold - prices[i]);
        // Какая максимальная прибыль, если на конец дня i у меня НЕТ акции?
        const newNotHold = Math.max(notHold, hold + prices[i] - fee);
 
        hold = newHold;
        notHold = newNotHold;
    }
 
    return notHold;
}