Best Time to Buy and Sell Stock IV LeetCode Solution

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

Dynamic Programming

Level of Question

Hard

Best Time to Buy and Sell Stock IV LeetCode Solution

Best Time to Buy and Sell Stock IV LeetCode Solution

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 ComplexitySpace Complexity
C++O(n * k)O(n + k)
JavaO(n * k)O(n * k)
JavaScriptO(n * k)O(n)
PythonO(n * k)O(k)
Scroll to Top