Welcome to Subscribe On Youtube
188. Best Time to Buy and Sell Stock IV
Description
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. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
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.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3] Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Constraints:
1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000
Solutions
Solution 1: Memoization Search
We design a function $dfs(i, j, k)$ to represent the maximum profit that can be obtained when starting from day $i$, completing at most $j$ transactions, and holding the stock with the current state $k$ (not holding the stock is represented by $0$, and holding the stock is represented by $1$). The answer is $dfs(0, k, 0)$.
The execution logic of the function $dfs(i, j, k)$ is as follows:
- If $i$ is greater than or equal to $n$, return $0$ directly.
- The i-th day can choose not to do anything, then $dfs(i, j, k) = dfs(i + 1, j, k)$.
- If $k > 0$, the i-th day can choose to sell the stock, then $dfs(i, j, k) = \max(dfs(i + 1, j - 1, 0) + prices[i], dfs(i + 1, j, k))$.
- Otherwise, if $j > 0$, the i-th day can choose to buy the stock, then $dfs(i, j, k) = \max(dfs(i + 1, j - 1, 1) - prices[i], dfs(i + 1, j, k))$.
The value of $dfs(i, j, k)$ is the maximum value of the above three cases.
During the process, we can use memoization search to save the results of each calculation to avoid repeated calculations.
The time complexity is $O(n \times k)$, and the space complexity is $O(n \times k)$, where $n$ and $k$ are the length of the prices array and the value of $k$, respectively.
Solution 2: Dynamic Programming
We can also use dynamic programming to define $f[i][j][k]$ as the maximum profit that can be obtained when completing at most j transactions (here we define the number of transactions as the number of purchases), and holding the stock with the current state k on the i-th day. The initial value of $f[i][j][k]$ is 0. The answer is $f[n - 1][k][0]$.
When $i = 0$, the stock price is $prices[0]$. For any $j$ \in [1, k]$, we have $f[0][j][1] = -prices[0]$, which means buying the stock on the 0-th day with a profit of $-prices[0]$.
When $i > 0$:
- If the i-th day does not hold the stock, it may be that the stock was held on the i-1-th day and sold on the i-th day, or the stock was not held on the i-1-th day and no operation was performed on the i-th day. Therefore, $f[i][j][0] = \max(f[i - 1][j][1] + prices[i], f[i - 1][j][0])$.
- If the i-th day holds the stock, it may be that the stock was not held on the i-1-th day and bought on the i-th day, or the stock was held on the i-1-th day and no operation was performed on the i-th day. Therefore, $f[i][j][1] = max(f[i - 1][j - 1][0] - prices[i], f[i - 1][j][1])$.
Therefore, when $i > 0$, we can get the state transition equation:
\[\begin{aligned} f[i][j][0] &= \max(f[i - 1][j][1] + prices[i], f[i - 1][j][0]) \\ f[i][j][1] &= \max(f[i - 1][j - 1][0] - prices[i], f[i - 1][j][1]) \end{aligned}\]The final answer is $f[n - 1][k][0]$.
The time complexity is $O(n \times k)$, and the space complexity is $O(n \times k)$, where $n$ and $k$ are the length of the prices array and the value of $k$, respectively.
We notice that the state $f[i][]$ only depends on the state $f[i - 1][]$, so we can optimize the first dimension of the space and reduce the space complexity to $O(k)$.
-
class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; int[][] f = new int[k + 1][2]; for (int j = 1; j <= k; ++j) { f[j][1] = -prices[0]; } for (int i = 1; i < n; ++i) { for (int j = k; j > 0; --j) { f[j][0] = Math.max(f[j][1] + prices[i], f[j][0]); f[j][1] = Math.max(f[j - 1][0] - prices[i], f[j][1]); } } return f[k][0]; } } -
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); int f[k + 1][2]; memset(f, 0, sizeof(f)); for (int j = 1; j <= k; ++j) { f[j][1] = -prices[0]; } for (int i = 1; i < n; ++i) { for (int j = k; j; --j) { f[j][0] = max(f[j][1] + prices[i], f[j][0]); f[j][1] = max(f[j - 1][0] - prices[i], f[j][1]); } } return f[k][0]; } }; -
class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: n = len(prices) if n < 2: return 0 # 3-D dp: n days * k completed transactions * 2 ops buy/sell # my understanding, one transaction, meaning both buy then sell completed dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)] for i in range(1, k + 1): dp[0][i][1] = -prices[0] # dp[][][ 0/1 ], 1 is buy, 0 is sell for i in range(1, n): for j in range(1, k + 1): dp[i][j][0] = max(dp[i - 1][j][1] + prices[i], dp[i - 1][j][0]) # [1] => sell happening <= that day dp[i][j][1] = max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1]) return dp[-1][k][0] ############## class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: @cache def dfs(i, j, k): 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) ############## import heapq import random class Solution(object): def findKthLargest(self, nums, k): """ :type A: List[int] :type k: int :rtype: int """ def quickselect(start, end, nums, k): if start == end: return nums[start] mid = partition(start, end, nums) if mid == k: return nums[mid] elif k > mid: return quickselect(mid + 1, end, nums, k) else: return quickselect(start, mid - 1, nums, k) def partition(start, end, nums): p = random.randrange(start, end + 1) pv = nums[p] nums[end], nums[p] = nums[p], nums[end] mid = start for i in range(start, end): if nums[i] >= pv: nums[i], nums[mid] = nums[mid], nums[i] mid += 1 nums[mid], nums[end] = nums[end], nums[mid] return mid return quickselect(0, len(nums) - 1, nums, k - 1) def maxProfit(self, k, prices): """ :type k: int :type prices: List[int] :rtype: int """ if not prices: return 0 stack = [] heap = [] v = p = 0 n = len(prices) ans = 0 while p < n: v = p while v < n - 1 and prices[v] >= prices[v + 1]: v += 1 p = v + 1 while p < n and prices[p] > prices[p - 1]: p += 1 while stack and prices[stack[-1][0]] > prices[v]: _v, _p = stack.pop() heap.append(prices[_p - 1] - prices[_v]) while stack and prices[stack[-1][1] - 1] < prices[p - 1]: heap.append(prices[stack[-1][1] - 1] - prices[v]) v, _ = stack.pop() stack.append((v, p)) heap += [prices[p - 1] - prices[v] for v, p in stack] if len(heap) < k: return sum(heap) self.findKthLargest(heap, k) return sum(heap[:k]) -
func maxProfit(k int, prices []int) int { f := make([][2]int, k+1) for j := 1; j <= k; j++ { f[j][1] = -prices[0] } for _, x := range prices[1:] { for j := k; j > 0; j-- { f[j][0] = max(f[j][1]+x, f[j][0]) f[j][1] = max(f[j-1][0]-x, f[j][1]) } } return f[k][0] } -
function maxProfit(k: number, prices: number[]): number { const f = Array.from({ length: k + 1 }, () => Array.from({ length: 2 }, () => 0)); for (let j = 1; j <= k; ++j) { f[j][1] = -prices[0]; } for (const x of prices.slice(1)) { for (let j = k; j; --j) { f[j][0] = Math.max(f[j][1] + x, f[j][0]); f[j][1] = Math.max(f[j - 1][0] - x, f[j][1]); } } return f[k][0]; } -
public class Solution { public int MaxProfit(int k, int[] prices) { int n = prices.Length; int[,] f = new int[k + 1, 2]; for (int j = 1; j <= k; ++j) { f[j, 1] = -prices[0]; } for (int i = 1; i < n; ++i) { for (int j = k; j > 0; --j) { f[j, 0] = Math.Max(f[j, 1] + prices[i], f[j, 0]); f[j, 1] = Math.Max(f[j - 1, 0] - prices[i], f[j, 1]); } } return f[k, 0]; } }