Best Time To Buy And Sell Stock With Cooldown

                                            
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) {
            return 0;
        }
        
        int buy = -prices[0];
        int sell = 0;
        int cooldown = 0;
        
        for (int i = 1; i < n; i++) {
            int prevBuy = buy;
            buy = max(buy, cooldown - prices[i]);
            cooldown = sell;
            sell = max(sell, prevBuy + prices[i]);
        }
        
        return sell;
    }
};

                                            
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n <= 1) {
            return 0;
        }
        
        int[] buy = new int[n];
        int[] sell = new int[n];
        
        buy[0] = -prices[0];
        buy[1] = Math.max(buy[0], -prices[1]);
        sell[0] = 0;
        sell[1] = Math.max(sell[0], buy[0] + prices[1]);
        
        for (int i = 2; i < n; i++) {
            buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        
        return sell[n - 1];
    }
}

                                            
class Solution(object):
    def maxProfit(self, prices):
        if not prices:
            return 0
        
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
        
        return dp[n-1][0]

                                            
int maxProfit(int* prices, int pricesSize) {
    if (pricesSize <= 1) {
        return 0;
    }
    
    int sold = 0, hold = -prices[0], rest = 0;
    
    for (int i = 1; i < pricesSize; i++) {
        int prev_sold = sold;
        sold = hold + prices[i];
        hold = fmax(hold, rest - prices[i]);
        rest = fmax(rest, prev_sold);
    }
    
    return fmax(sold, rest);
}

                                            
public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices == null || prices.Length == 0) {
            return 0;
        }
        
        int n = prices.Length;
        int[] dp = new int[n];
        
        int buy = -prices[0];
        int sell = 0;
        int cooldown = 0;
        
        for (int i = 1; i < n; i++) {            
            int prev_buy = buy;
            buy = Math.Max(buy, cooldown - prices[i]);
            cooldown = Math.Max(cooldown, sell);
            sell = prev_buy + prices[i];
            
            dp[i] = Math.Max(dp[i - 1], sell);
        }
        
        return dp[n - 1];
    }
}

                                            
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let buy = -prices[0];
    let sell = 0;
    let cooldown = 0;
    
    for (let i = 1; i < prices.length; i++) {
        let prevBuy = buy;
        buy = Math.max(buy, cooldown - prices[i]);
        cooldown = sell;
        sell = Math.max(sell, prevBuy + prices[i]);
    }
    
    return sell;
};

                                            
function maxProfit(prices: number[]): number {
    const n = prices.length;
    const dp: number[][] = new Array(n).fill(0).map(() => new Array(2).fill(0));

    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], (i > 1 ? dp[i - 2][0] : 0) - prices[i]);
    }

    return dp[n - 1][0];
};

                                            
class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $n = count($prices);
        $dp = array_fill(0, $n, array_fill(0, 2, 0));
        $dp[0][0] = 0;
        $dp[0][1] = -$prices[0];

        for ($i = 1; $i < $n; $i++) {
            $dp[$i][0] = max($dp[$i - 1][0], $dp[$i - 1][1] + $prices[$i]);
            $dp[$i][1] = max($dp[$i - 1][1], ($i > 1 ? $dp[$i - 2][0] : 0) - $prices[$i]);
        }

        return $dp[$n - 1][0];
    }
}

                                            
class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count < 2 {
            return 0
        }
        
        var buy = Array(repeating: 0, count: prices.count)
        var sell = Array(repeating: 0, count: prices.count)
        var cooldown = Array(repeating: 0, count: prices.count)
        
        buy[0] = -prices[0]
        
        for i in 1..<prices.count {
            buy[i] = max(cooldown[i-1] - prices[i], buy[i-1])
            sell[i] = buy[i-1] + prices[i]
            cooldown[i] = max(cooldown[i-1], sell[i-1])
        }
        
        return max(sell.last!, cooldown.last!)
    }
}

                                            
class Solution {
    fun maxProfit(prices: IntArray): Int {
        if (prices.isEmpty()) {
            return 0
        }
        
        var buy = -prices[0]
        var sell = 0
        var cooldown = 0
        
        for (i in 1 until prices.size) {
            val newBuy = maxOf(buy, cooldown - prices[i])
            val newSell = maxOf(sell, buy + prices[i])
            val newCooldown = maxOf(cooldown, sell)
            
            buy = newBuy
            sell = newSell
            cooldown = newCooldown
        }
        
        return sell
    }
}

                                            
func maxProfit(prices []int) int {
    if len(prices) <= 1 {
        return 0
    }
    
    dp := make([][2]int, len(prices))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    dp[1][0] = max(dp[0][0], dp[0][1]+prices[1])
    dp[1][1] = max(dp[0][1], dp[0][0]-prices[1])

    for i := 2; i < len(prices); i++ {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i])
    }
    
    return dp[len(prices)-1][0]
}

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

                                            
# @param {Integer[]} prices
# @return {Integer}
def max_profit(prices)
    n = prices.length
    return 0 if n <= 1
    
    buy = Array.new(n, 0)
    sell = Array.new(n, 0)
    cooldown = Array.new(n, 0)
    
    buy[0] = -prices[0]
    
    (1...n).each do |i|
        if i == 1
            buy[i] = [buy[i - 1], -prices[i]].max
        else
            buy[i] = [buy[i - 1], cooldown[i - 1] - prices[i]].max
        end
        sell[i] = [sell[i - 1], buy[i - 1] + prices[i]].max
        cooldown[i] = [cooldown[i - 1], sell[i - 1]].max
    end
    
    [sell[n - 1], cooldown[n - 1]].max
end

                                            
object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        if (prices.isEmpty) return 0

        var hold = -prices(0)
        var sell = 0
        var cooldown = 0

        for (i <- 1 until prices.length) {
            val prevHold = hold
            hold = math.max(hold, cooldown - prices(i))
            cooldown = sell
            sell = math.max(sell, prevHold + prices(i))
        }

        return sell
    }
}

                                            
impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let n = prices.len();
        if n < 2 {
            return 0;
        }

        let mut dp = vec![vec![0; 2]; n];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[1][0] = dp[0][0].max(dp[0][1] + prices[1]);
        dp[1][1] = dp[0][1].max(dp[0][0] - prices[1]);

        for i in 2..n {
            dp[i][0] = dp[i - 1][0].max(dp[i - 1][1] + prices[i]);
            dp[i][1] = dp[i - 1][1].max(dp[i - 2][0] - prices[i]);
        }

        dp[n - 1][0]
    }
}

To solve this coding challenge of finding the maximum profit from stock transactions with a cooldown period, you can use dynamic programming. The challenge requires that you calculate the optimal buy and sell points while adhering to a mandatory cooldown period that disallows buying the stock on the day immediately following a sale. We need to maintain two states for each day:

The maximum profit if we do not hold a stock at the end of the ith day.
The maximum profit if we hold a stock at the end of the ith day.

Here's a detailed step-by-step explanation of the methodology used to solve this problem:

Explanation

Initialization:

Check if the prices array is empty. If it is empty, return 0 because no transactions can be performed.
Initialize a 2D list (
dp

) where each element is a list containing two elements:

The first element (0th index) represents the maximum profit on the ith day if we do not hold a stock.
The second element (1st index) represents the maximum profit on the ith day if we hold a stock.

Base Case:

On the first day:

If we do not hold a stock, the profit is 0.
If we hold a stock, the profit is
-prices[0]

because we have spent money to buy the stock.

State Transition:

For each subsequent day:

If we do not hold a stock on the ith day, two scenarios are possible:

We did not hold a stock on the (i-1)th day.
We sold the stock on the ith day which we had bought earlier (i.e., we had the stock on the (i-1)th day and sold it on the ith day). Additionally, we can't buy it back the very next day, hence there should be a cooldown. So we need to consider the maximum profit from i-2th day if such a day exists.

If we hold a stock on the ith day, two scenarios are possible:

We held a stock on the (i-1)th day.
We bought a new stock on the ith day. For this, we should have been in the state where we were not holding a stock on the (i-1)th day and we have subtracted the price of the stock from the profit of (i-1)th day profit.

Final Result:

The maximum profit will be the value where we do not hold any stock on the last day.

Detailed Steps in Pseudocode

                                            
# Define a function to calculate maximum profit with cooldown
Function maxProfit(prices):
    # If there are no prices (empty list), return 0 as no profit can be made
    If prices is empty:
        Return 0
    
    # Find the length of the prices list
    n = length of prices
    
    # Initialize dp list to keep track of profits with each day’s states
    dp = list of [0, 0] repeated n times  # dp[i][0]: max profit not holding stock, dp[i][1]: max profit holding stock
    
    # Initialize the base case for the first day
    dp[0][0] = 0  # No profit if we do not hold the stock
    dp[0][1] = -prices[0]  # Profit will be negative of the price if we buy the stock
    
    # Iterate through each day starting from the second day
    For i from 1 to n-1:
        # Maximum profit not holding a stock on day i
        # Two options: either we are not holding from previous day or we sold today
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        
        # Maximum profit holding a stock on day i
        # Two options: either we were holding from previous day or we bought today
        If i > 1:
            dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
        Else:
            dp[i][1] = max(dp[i-1][1], -prices[i])
    
    # Return the result, which is the max profit on the last day not holding the stock
    Return dp[n-1][0]

This solution efficiently calculates the maximum profit that can be achieved while observing the cooldown constraint by leveraging dynamic programming and state transitions. The core idea is to keep track of the maximum profit under two states for each day, culminating in the optimal solution. Remember, the key constraints revolve around not being able to make multiple transactions at once and ensuring a day of cooldown after selling stock before buying again. The pseudocode provides a clear guideline on how to implement this logic step-by-step.