Problem Statement
Stock Trader with Cooldown
You are a stock trader who wants to maximize profit by buying and selling stocks. However, after you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Given an array prices where prices[i] is the price of a given stock on the ith day, your task is to 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 restrictions:
- After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
- You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Examples
Example 1:
Input: prices = [1, 2, 3, 0, 2]
Output: 3
Explanation: The transactions are: Buy on day 0 (price = 1), sell on day 2 (price = 3), cooldown on day 3, and buy on day 4 (price = 2). The total profit is 3 - 1 + 0 = 2.
Example 2:
Input: prices = [1]
Output: 0
Explanation: There's only one day, so you can't make any transaction and the max profit = 0.
Constraints
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
Problem Breakdown
To solve this problem, we need to:
- The key insight is to use dynamic programming to track the maximum profit in three states: buying, selling, and cooldown.
- At each day, we have multiple options: buy, sell, or do nothing, and we want to maximize our profit.
- The cooldown period after selling means we need to consider the state from two days ago when making a buying decision.
- We can use a state machine approach to model the transitions between different states.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Stock Trader with Cooldown
You are a stock trader who wants to maximize profit by buying and selling stocks. However, after you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Given an array prices where prices[i] is the price of a given stock on the ith day, your task is to 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 restrictions:
- After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
- You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Examples
Example 1:
The transactions are: Buy on day 0 (price = 1), sell on day 2 (price = 3), cooldown on day 3, and buy on day 4 (price = 2). The total profit is 3 - 1 + 0 = 2.
Example 2:
There's only one day, so you can't make any transaction and the max profit = 0.
Problem Breakdown
Constraints:
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
Key Insights:
The key insight is to use dynamic programming to track the maximum profit in three states: buying, selling, and cooldown.
At each day, we have multiple options: buy, sell, or do nothing, and we want to maximize our profit.
The cooldown period after selling means we need to consider the state from two days ago when making a buying decision.
We can use a state machine approach to model the transitions between different states.
Real-World Application
This problem has several practical applications:
Stock Trading
Optimizing trading strategies with mandatory rest periods between transactions.
Cooling-off Periods
Modeling financial decisions with regulatory cooling-off periods.
Trading Restrictions
Handling time-based restrictions in automated trading systems.