Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2 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.
The core challenge of this problem is to maximize the profit from at most k transactions. A transaction consists of buying and then selling one share of the stock. The constraint is that you cannot engage in multiple transactions simultaneously, meaning you must sell the stock before you can buy again.
This problem is significant in financial markets where traders aim to maximize their returns by buying and selling stocks at optimal times. A common pitfall is to assume that you can buy and sell on the same day or engage in multiple transactions simultaneously, which is not allowed.
To solve this problem, we can use dynamic programming. The idea is to maintain a table where the entry at index i and j represents the maximum profit achievable using at most i transactions up to day j.
A naive solution would involve trying all possible pairs of buy and sell days, which would be computationally expensive and inefficient. This approach has a time complexity of O(n^2) for each transaction, making it impractical for large inputs.
We can optimize the solution using dynamic programming. The idea is to use two arrays: dp and minPrice. The dp array will store the maximum profit up to day j with at most i transactions, and the minPrice array will store the minimum price encountered so far for each transaction.
1. Initialize a 2D array dp where dp[i][j] represents the maximum profit using at most i transactions up to day j.
2. Iterate over the number of transactions from 1 to k.
3. For each transaction, iterate over the days from 1 to n.
4. Update the minPrice for each transaction and calculate the maximum profit.
/**
* @param {number[]} prices
* @param {number} k
* @return {number}
*/
function maxProfit(k, prices) {
const n = prices.length;
if (n == 0) return 0;
// If k is greater than n/2, then it's equivalent to an unlimited number of transactions
if (k > n / 2) {
let maxProfit = 0;
for (let i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
const dp = Array.from({ length: k + 1 }, () => Array(n).fill(0));
for (let i = 1; i <= k; i++) {
let minPrice = prices[0];
for (let j = 1; j < n; j++) {
minPrice = Math.min(minPrice, prices[j] - dp[i - 1][j - 1]);
dp[i][j] = Math.max(dp[i][j - 1], prices[j] - minPrice);
}
}
return dp[k][n - 1];
}
// Example usage:
console.log(maxProfit(2, [2, 4, 1])); // Output: 2
console.log(maxProfit(2, [3, 2, 6, 5, 0, 3])); // Output: 7
The time complexity of the optimized solution is O(k * n), where k is the number of transactions and n is the number of days. The space complexity is also O(k * n) due to the 2D array used for dynamic programming.
1. If the number of days n is 0, the maximum profit is 0.
2. If k is greater than n/2, it is equivalent to an unlimited number of transactions.
3. If the prices array is strictly decreasing, the maximum profit is 0.
To test the solution comprehensively, consider the following test cases:
k is greater than n/2.1. Break down the problem into smaller subproblems and solve them using dynamic programming.
2. Consider edge cases and constraints to ensure the solution is robust.
3. Practice similar problems to improve problem-solving skills and understand different approaches.
In this blog post, we discussed the problem of finding the best time to buy and sell stock with at most k transactions. We explored a dynamic programming approach to solve the problem efficiently and analyzed its time and space complexity. By understanding and practicing such problems, you can improve your problem-solving skills and apply these techniques to other similar challenges.