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.
Constraints:
1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000#188 Best Time to Buy and Sell Stock IV asks you to maximize profit from stock prices with at most k transactions. The key challenge is deciding when to buy and sell while respecting the transaction limit. A common strategy is to model the problem using dynamic programming.
Define DP states that track the maximum profit at a given day and transaction count. One typical formulation uses states for buy and sell operations across up to k transactions. For each price, update the best profit achievable after buying or selling using previously computed results. This ensures each transaction pair (buy + sell) is counted correctly.
An important optimization occurs when k ≥ n/2 (where n is the number of days). In this case, the constraint effectively disappears and the problem reduces to the unlimited transactions version, which can be solved greedily.
The optimized DP solution runs in O(n × k) time while maintaining efficient state transitions with O(k) or O(n × k) space depending on implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with k Transactions | O(n × k) | O(k) or O(n × k) |
| Greedy (when k ≥ n/2) | O(n) | O(1) |
Tushar Roy - Coding Made Simple
This approach involves using a dynamic programming table where dp[i][j] represents the maximum profit obtainable on the ith day with up to j transactions. The state can be compressed by keeping track of two main variables: one for the max profit holding deals and one for not holding deals.
Time Complexity: O(kn), where n is the number of days and k is the number of allowed transactions.
Space Complexity: O(n), as we are storing profit states for each day.
1public class Solution {
2 public int maxProfit(int k, int[] prices) {
3 int n = prices.length;
4 if (n == 0) return 0;
5 if (k >= n / 2) {
6 int profit = 0;
7 for (int i = 1; i < n; i++)
8 profit += Math.max(0, prices[i] - prices[i - 1]);
9 return profit;
10 }
11 int[] profits = new int[n];
12 for (int j = 0; j < k; j++) {
13 int maxDiff = -prices[0];
14 int prevProfit = 0;
15 for (int i = 1; i < n; i++) {
16 int temp = profits[i];
17 profits[i] = Math.max(profits[i - 1], prices[i] + maxDiff);
18 maxDiff = Math.max(maxDiff, prevProfit - prices[i]);
19 prevProfit = temp;
20 }
21 }
22 return profits[n - 1];
23 }
24}The Java implementation follows the same logic as the Python and C++ codes with adjustment to Java syntax. We use an array to update profit possibilities, using previous profits and maximum price differences.
This method is a classical dynamic programming solution where we maintain a 2D array dp[j][i], that contains the maximum profit achievable having executed up to j transactions on the ith day.
Time Complexity: O(kn).
Space Complexity: O(kn), uses additional space for the DP table.
1function maxProfit(k, prices) {
2 Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the stock buy-and-sell problems are commonly asked in FAANG and other top tech company interviews. Interviewers often test candidates on dynamic programming optimization and recognizing when the problem reduces to the unlimited transactions case.
Dynamic programming arrays or variables are most suitable for this problem. They store the best profit after each buy or sell operation across transactions. Some optimized solutions compress the DP table into one-dimensional arrays for better space efficiency.
The optimal approach typically uses dynamic programming to track profits across up to k transactions. By maintaining states for buying and selling, you can compute the best profit for each day while respecting the transaction limit. This approach runs in O(n × k) time.
This version introduces a limit of k transactions, making it more complex than earlier variants. Unlike simpler problems that allow unlimited trades or just one transaction, you must carefully track transaction counts using dynamic programming.
Utilizes a 2D array dynamically allocated for handling transaction evaluations, updating them continuously using previous transaction values and price differences for optimal profit assessment.