HardNo. 0188
Best Time to Buy and Sell Stock IV — LeetCode 188 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- On a study list
- Top Interview 150
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve.
Example
- Input
- k = 2, prices = [2,4,1]
- Output
- 2
- Explanation
- Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Python solution
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i >= len(prices):
return 0
ans = dfs(i + 1, j, k)
if k:
ans = max(ans, prices[i] + dfs(i + 1, j, 0))
elif j:
ans = max(ans, -prices[i] + dfs(i + 1, j - 1, 1))
return ans
return dfs(0, k, 0)Complexity
- Time
- O(n × k)
- Space · auxiliary
- O(n × k)where n and k are the length of the prices array and the value of k, respectively
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 188. Best Time to Buy and Sell Stock IV 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
| No. | Problem | Difficulty |
|---|---|---|
| 0121 | Best Time to Buy and Sell Stock | Easy |
| 0198 | House Robber | Medium |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
| 0063 | Unique Paths II | Medium |
Frequently asked questions
- How hard is LeetCode 188. Best Time to Buy and Sell Stock IV?
LeetCode 188. Best Time to Buy and Sell Stock IV is rated Hard on LeetCode.
- What is the time complexity of LeetCode 188. Best Time to Buy and Sell Stock IV?
The Python solution on this page runs in O(n × k).
- What is the space complexity of LeetCode 188. Best Time to Buy and Sell Stock IV?
The Python solution on this page uses O(n × k), where n and k are the length of the prices array and the value of k, respectively auxiliary space.
- What topics does LeetCode 188. Best Time to Buy and Sell Stock IV cover?
LeetCode 188. Best Time to Buy and Sell Stock IV is tagged Array and Dynamic Programming on LeetCode.