Last updated on January 29th, 2025 at 02:12 am
Here, we see the Best Time to Buy and Sell Stock IV LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Level of Question
Hard

Best Time to Buy and Sell Stock IV LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Dynamic Programming”. This is evident because the problem involves breaking down the solution into smaller overlapping subproblems, storing intermediate results, and reusing them to compute the final result. Specifically, the problem is a variation of the 0/1 Knapsack Problem, where we are trying to maximize profit by selecting at most k
transactions.
3. Code Implementation in Different Languages
3.1 Best Time to Buy and Sell Stock IV C++
class Solution { public: int maxProfit(int k, vector<int>& prices) { vector<int> profits; stack<pair<int, int>> vps; int v; int p = -1; for (;;) { for (v = p+1; (v+1 < prices.size()) && (prices[v] >= prices[v+1]); ++v); for (p = v ; (p+1 < prices.size()) && (prices[p] <= prices[p+1]); ++p); if (v == p) { break; } while ((!vps.empty()) && (prices[v] <= prices[vps.top().first])) { profits.push_back(prices[vps.top().second] - prices[vps.top().first]); vps.pop(); } while ((!vps.empty()) && (prices[p] >= prices[vps.top().second])) { profits.push_back(prices[vps.top().second] - prices[v]); v = vps.top().first; vps.pop(); } vps.emplace(v, p); } while (!vps.empty()) { profits.push_back(prices[vps.top().second] - prices[vps.top().first]); vps.pop(); } int ret; if (profits.size() <= k) { ret = accumulate(profits.begin(), profits.end(), 0); } else { nth_element(profits.begin(), profits.end() - k, profits.end()); ret = accumulate(profits.end() - k, profits.end(), 0); } return ret; } };
3.2 Best Time to Buy and Sell Stock IV Java
class Solution { public int maxProfit(int k, int[] prices) { int n = prices.length; if (n <= 1) return 0; if (k >= n/2) { int maxPro = 0; for (int i = 1; i < n; i++) { if (prices[i] > prices[i-1]) maxPro += prices[i] - prices[i-1]; } return maxPro; } int[][] dp = new int[k+1][n]; for (int i = 1; i <= k; i++) { int localMax = dp[i-1][0] - prices[0]; for (int j = 1; j < n; j++) { dp[i][j] = Math.max(dp[i][j-1], prices[j] + localMax); localMax = Math.max(localMax, dp[i-1][j] - prices[j]); } } return dp[k][n-1]; } }
3.3 Best Time to Buy and Sell Stock IV JavaScript
var maxProfit = function(k, prices) { if(prices.length == 0) return 0; if(k > (prices.length / 2) ){ let profit = 0; for(let i = 1; i < prices.length; i++){ if(prices[i] > prices[i - 1]){ profit += prices[i] - prices[i - 1]; } } return profit; } else{ let dp = new Array(prices.length).fill(0); let size = prices.length; for(let t = 1; t <= k; t++){ let min = prices[0]; let max = 0; for(let i = 0; i < size; i++){ min = Math.min(min, prices[i] - dp[i]); max = Math.max(max, prices[i] - min); dp[i] = max } } return dp.pop(); } };
3.4 Best Time to Buy and Sell Stock IV Python
class Solution(object): def maxProfit(self, k, prices): if k == 0: return 0 dp = [[1000, 0] for _ in range(k + 1)] for price in prices: for i in range(1, k + 1): dp[i][0] = min(dp[i][0], price - dp[i - 1][1]) dp[i][1] = max(dp[i][1], price - dp[i][0]) return dp[k][1]
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n * k) | O(n + k) |
Java | O(n * k) | O(n * k) |
JavaScript | O(n * k) | O(n) |
Python | O(n * k) | O(k) |