algoadvance

Leetcode 309. Best Time to Buy and Sell Stock with Cooldown

Problem Statement

You are given an array where prices[i] is the price of a given stock on the i-th day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following constraints:

1. After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
2. You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Clarifying Questions

1. Can I assume that the input array prices is non-empty?
   • Yes, you can assume the input array contains at least one price value.
2. What is the range of prices[i]?
   • Prices can range from 0 to 10,000.
3. Are negative prices allowed?
   • No, stock prices are non-negative.

Strategy

To achieve the maximum profit given the constraints, the problem can be approached using dynamic programming. We will maintain three states:

1. Hold: The maximum profit while currently holding a stock.
2. Sell: The maximum profit after selling a stock.
3. CoolDown: The maximum profit during a cooldown period.

Using these states, the transitions between days can be described as:

• From holding stock: You can either keep holding or sell the stock.
• From selling stock: After selling, you enter a cooldown period.
• From cooldown period: You can either buy a new stock or stay in the cooldown.

The optimal solution will involve iterating through the prices array and updating the states according to these transitions.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        if (prices.empty()) return 0;
        
        int n = prices.size();
        
        // Initialize dp arrays
        std::vector<int> hold(n, 0);
        std::vector<int> sell(n, 0);
        std::vector<int> cool(n, 0);
        
        hold[0] = -prices[0]; // On day 0, if we hold a stock, the profit is negative of the price
        
        for (int i = 1; i < n; ++i) {
            hold[i] = std::max(hold[i - 1], cool[i - 1] - prices[i]);
            sell[i] = hold[i - 1] + prices[i];
            cool[i] = std::max(cool[i - 1], sell[i - 1]);
        }
        
        // The result will be the maximum profit on the last day after selling or being in cooldown
        return std::max(sell[n - 1], cool[n - 1]);
    }
};

Explanation

• Initialization: Start by initializing the hold, sell, and cool vectors for day 0. hold[0] is initialized to -prices[0] because if we buy the stock on the first day, our profit becomes negative of that day’s price.

• State transitions for each day:
  • hold[i]: Can be derived by either holding the stock from hold[i-1] or buying a new stock after a cooldown (cool[i-1] - prices[i]).
  • sell[i]: Can be derived by selling the stock that was held (hold[i-1] + prices[i]).
  • cool[i]: Can be derived either from still being in cooldown (cool[i-1]) or entering cooldown from a sell (sell[i-1]).
• Result: The maximum profit on the last day can be in the sell or cool state.

Time Complexity

The time complexity is ( O(n) ) because we iterate through the prices array exactly once, updating the states in constant time for each day. The space complexity is ( O(n) ) due to the storage of dynamic programming arrays hold, sell, and cool.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?