Best Time to Buy and Sell Stock IV LeetCode Solution

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

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.

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;
}
};```Code language: PHP (php)```

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];
}
}```Code language: JavaScript (javascript)```

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();
}
};```Code language: JavaScript (javascript)```

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]``````
Scroll to Top