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}C# implementation keeps the same control flow and algorithm as other languages, using an array to maintain profit evaluation for each potential stock transaction by iterating over possible transaction days.
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.
1#include <stdlib.h>
2#include <string.h>
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.
We use malloc to create a 2D array for storing profit states. The approach involves calculating maximum difference adjustments each time a potential transaction point is evaluated, allowing a full exploration of transaction possibilities up to k times.