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
![Best Time to Buy and Sell Stock IV LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
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 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]