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

309. Best Time to Buy and Sell Stock with Cooldown

Medium
Arrays61.8% acceptance

Given an integer array stock_prices where stock_prices[i] represents the price of a stock on day i, compute the maximum profit achievable by performing any number of buy and sell operations with the following restrictions: After selling a stock, you must wait one day before buying again (cooldown period). You cannot hold more than one stock at a time. Return the maximum profit as an integer.

Example 1

Input: [4, 1, 5, 3, 6, 4]

Output: 6

Explanation: Buy at 1, sell at 5 (profit 4), cooldown, buy at 3, sell at 6 (profit 3), total profit 7. But cooldown after selling at 5 means you can only buy at 3, so total profit is 6.

Example 2

Input: [2, 2, 2, 2, 2]

Output: 0

Explanation: No profitable transactions.

Example 3

Input: [7, 6, 4, 3, 1]

Output: 0

Explanation: Prices decrease, no profit possible.

Constraints

  • 1 <= len(stock_prices) <= 5000
  • 0 <= stock_prices[i] <= 1000 for all valid i
Python (current runtime)

Case 1

Input: [3, 2, 6, 5, 0, 3]

Expected: 7

Case 2

Input: [1, 3, 2, 8, 4, 9]

Expected: 11

Case 3

Input: [5, 4, 3, 2, 1]

Expected: 0

Case 4

Input: [1, 2, 4, 2, 5, 7, 2, 4, 9, 0]

Expected: 13