Best Time to Buy and Sell Stock with Cooldown — LeetCode 309 Python Solution
MediumArrayDynamic Programming
- Problem
- #309
- Pattern
- Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve.
Example
- Input
- prices = [1,2,3,0,2]
- Output
- 3
- Explanation
- transactions = [buy, sell, cooldown, buy, sell]
Python solution
Python
class Solution:
def maxProfit(self, prices: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= len(prices):
return 0
ans = dfs(i + 1, j)
if j:
ans = max(ans, prices[i] + dfs(i + 2, 0))
else:
ans = max(ans, -prices[i] + dfs(i + 1, 1))
return ans
return dfs(0, 0)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the length of the array prices auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 309. Best Time to Buy and Sell Stock with Cooldown is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
On a study list
This problem is on NeetCode 150.
Frequently asked questions
- How hard is LeetCode 309. Best Time to Buy and Sell Stock with Cooldown?
- LeetCode 309. Best Time to Buy and Sell Stock with Cooldown is rated Medium on LeetCode.
- What is the time complexity of LeetCode 309. Best Time to Buy and Sell Stock with Cooldown?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 309. Best Time to Buy and Sell Stock with Cooldown?
- The Python solution on this page uses O(n), where n is the length of the array prices auxiliary space.
- What topics does LeetCode 309. Best Time to Buy and Sell Stock with Cooldown cover?
- LeetCode 309. Best Time to Buy and Sell Stock with Cooldown is tagged Array and Dynamic Programming on LeetCode.