Last updated on October 9th, 2024 at 06:10 pm

Here, We see **Best Time to Buy and Sell Stock IV LeetCode Solution**. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

*List of all LeetCode Solution*

*List of all LeetCode Solution*

## Topics

Dynamic Programming

## Level of Question

Hard

**Best Time to Buy and Sell Stock IV LeetCode Solution**

## Table of Contents

**Problem Statement**

You are given an integer array `prices`

where `prices[i]`

is the price of a given stock on the `i`

day, and an integer ^{th}`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.

**1. Best Time to Buy and Sell Stock IV LeetCode Solution 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; } };

**2. Best Time to Buy and Sell Stock IV LeetCode Solution 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. Best Time to Buy and Sell Stock IV LeetCode Solution 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(); } };

**4. Best Time to Buy and Sell Stock IV LeetCode Solution 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]