309. Best Time to Buy and Sell Stock with Cooldown

leetcode medium

#array#csharp#leetcode#math#medium

Task

Дан массив prices, где prices[i] — цена данной акции в i-й день.

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

После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).

Пример:

Input: prices = [1]

Output: 0

C# solution

matched/original

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices.Length == 0) return 0;
        
        int hold = -prices[0];
        int sold = 0;
        int cooldown = 0;
        
        for (int i = 1; i < prices.Length; i++) {
            int newHold = Math.Max(hold, cooldown - prices[i]);
            int newSold = hold + prices[i];
            int newCooldown = Math.Max(cooldown, sold);
            
            hold = newHold;
            sold = newSold;
            cooldown = newCooldown;
        }
        
        return Math.Max(sold, cooldown);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        
        int hold = -prices[0];
        int sold = 0;
        int cooldown = 0;
        
        for (int i = 1; i < prices.size(); i++) {
            int newHold = max(hold, cooldown - prices[i]);
            int newSold = hold + prices[i];
            int newCooldown = max(cooldown, sold);
            
            hold = newHold;
            sold = newSold;
            cooldown = newCooldown;
        }
        
        return max(sold, cooldown);
    }
}

Java solution

matched/original

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        
        int hold = -prices[0];
        int sold = 0;
        int cooldown = 0;
        
        for (int i = 1; i < prices.length; i++) {
            int newHold = Math.max(hold, cooldown - prices[i]);
            int newSold = hold + prices[i];
            int newCooldown = Math.max(cooldown, sold);
            
            hold = newHold;
            sold = newSold;
            cooldown = newCooldown;
        }
        
        return Math.max(sold, cooldown);
    }
}

JavaScript solution

matched/original

var maxProfit = function(prices) {
    if (prices.length === 0) return 0;
    
    let hold = -prices[0];
    let sold = 0;
    let cooldown = 0;
    
    for (let i = 1; i < prices.length; i++) {
        let newHold = Math.max(hold, cooldown - prices[i]);
        let newSold = hold + prices[i];
        let newCooldown = Math.max(cooldown, sold);
        
        hold = newHold;
        sold = newSold;
        cooldown = newCooldown;
    }
    
    return Math.max(sold, cooldown);
};

Python solution

matched/original

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        n = len(prices)
        hold = -prices[0]
        sold = 0
        cooldown = 0
        
        for i in range(1, n):
            new_hold = max(hold, cooldown - prices[i])
            new_sold = hold + prices[i]
            new_cooldown = max(cooldown, sold)
            
            hold = new_hold
            sold = new_sold
            cooldown = new_cooldown
        
        return max(sold, cooldown)

Go solution

matched/original

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    
    hold := -prices[0]
    sold := 0
    cooldown := 0
    
    for i := 1; i < len(prices); i++ {
        newHold := max(hold, cooldown - prices[i])
        newSold := hold + prices[i]
        newCooldown := max(cooldown, sold)
        
        hold = newHold
        sold = newSold
        cooldown = newCooldown
    }
    
    return max(sold, cooldown)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Инициализация состояний

Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи.

Обновление состояний

Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

Определение максимальной прибыли

В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎