Best Time to Buy and Sell Stock IV – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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.
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.
Constraints:
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
C++ Best Time to Buy and Sell Stock IV LeetCode Solution
class Solution {
public:
int maxProfit(int k, vector<int> &prices) {
int n = (int)prices.size(), ret = 0, v, p = 0;
priority_queue<int> profits;
stack<pair<int, int> > vp_pairs;
while (p < n) {
// find next valley/peak pair
for (v = p; v < n - 1 && prices[v] >= prices[v+1]; v++);
for (p = v + 1; p < n && prices[p] >= prices[p-1]; p++);
// save profit of 1 transaction at last v/p pair, if current v is lower than last v
while (!vp_pairs.empty() && prices[v] < prices[vp_pairs.top().first]) {
profits.push(prices[vp_pairs.top().second-1] - prices[vp_pairs.top().first]);
vp_pairs.pop();
}
// save profit difference between 1 transaction (last v and current p) and 2 transactions (last v/p + current v/p),
// if current v is higher than last v and current p is higher than last p
while (!vp_pairs.empty() && prices[p-1] >= prices[vp_pairs.top().second-1]) {
profits.push(prices[vp_pairs.top().second-1] - prices[v]);
v = vp_pairs.top().first;
vp_pairs.pop();
}
vp_pairs.push(pair<int, int>(v, p));
}
// save profits of the rest v/p pairs
while (!vp_pairs.empty()) {
profits.push(prices[vp_pairs.top().second-1] - prices[vp_pairs.top().first]);
vp_pairs.pop();
}
// sum up first k highest profits
for (int i = 0; i < k && !profits.empty(); i++) {
ret += profits.top();
profits.pop();
}
return ret;
}
};
Java Best Time to Buy and Sell Stock IV LeetCode Solution
/**
* dp[i, j] represents the max profit up until prices[j] using at most i transactions.
* dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj]) { jj in range of [0, j-1] }
* = max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj]))
* dp[0, j] = 0; 0 transactions makes 0 profit
* dp[i, 0] = 0; if there is only one price data point you can't make any transaction.
*/
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n <= 1)
return 0;
//if k >= n/2, then you can make maximum number of transactions.
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];
}
Python 3 Best Time to Buy and Sell Stock IV LeetCode Solution
def maxProfit4(self, k, prices):
n = len(prices)
if n < 2:
return 0
# k is big enougth to cover all ramps.
if k >= n / 2:
return sum(i - j
for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
globalMax = [[0] * n for _ in xrange(k + 1)]
for i in xrange(1, k + 1):
# The max profit with i transations and selling stock on day j.
localMax = [0] * n
for j in xrange(1, n):
profit = prices[j] - prices[j - 1]
localMax[j] = max(
# We have made max profit with (i - 1) transations in
# (j - 1) days.
# For the last transation, we buy stock on day (j - 1)
# and sell it on day j.
globalMax[i - 1][j - 1] + profit,
# We have made max profit with (i - 1) transations in
# (j - 1) days.
# For the last transation, we buy stock on day j and
# sell it on the same day, so we have 0 profit, apparently
# we do not have to add it.
globalMax[i - 1][j - 1], # + 0,
# We have made profit in (j - 1) days.
# We want to cancel the day (j - 1) sale and sell it on
# day j.
localMax[j - 1] + profit)
globalMax[i][j] = max(globalMax[i][j - 1], localMax[j])
return globalMax[k][-1]
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below