Best Time To Buy And Sell Stock Iv - Leetcode Solution

Problem Statement: Say you have an array for which the ith 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 (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

Solution: The first approach that comes to the mind is to use dynamic programming to solve this problem. We can use a 2-D DP array where dp[i][j] represents the maximum profit that can be earned by doing at least one transaction up to day i, considering at most j transactions. We can define three variables buy, sell and trans. The buy variable tells us the minimum price to buy the stock till that day, the sell variable tells us the maximum profit that can be earned till i considering only one transaction and the trans variable represents the maximum profit earned till i considering j transactions. We can use the following recurrence relation to calculate the dp[i][j] value:

dp[i][j] = max(dp[i - 1][j], prices[i] - buy) trans = max(trans, sell - prices[i]) sell = max(sell, dp[i-1][j-1] - prices[i-1] + prices[i]) buy = min(buy, prices[i])

The time complexity of this approach is O(n*k). But it will give us a Time Limit Exceeded (TLE) error on Leetcode for test cases where k and n are large.

To optimize the above approach, we can use a faster algorithm for solving the problem. Consider the given array of stock prices. We can visualize it as a graph where the x-axis represents the days and the y-axis represents the price of the stock. By inspection, we can see that the maximum profit that can be earned by doing at most k transactions is the sum of the maximum profits that can be earned for each consecutive pair of days where the first day is spent buying the stock and the second day is spent selling the stock. For example, if k=2 and prices=[3,2,6,5,0,3], then we can buy on day 1 and sell on day 2 to get a profit of 0-2=-2, and buy on day 3 and sell on day 5 to get a profit of 0-6=-6. The total profit is -2+-6=-8. However, we can also buy on day 1 and sell on day 3 to get a profit of 0-3=-3, and buy on day 4 and sell on day 5 to get a profit of 0-3=-3. The total profit is -3+-3=-6 which is greater than -8.

We can use the above observation to design an algorithm to solve the problem. We can use a dynamic programming approach where we maintain three 1-D arrays buy, sell, and profit (where profit is the maximum profit that can be earned by doing at most k transactions up to that day). We can use the following recurrence relation to calculate the profit value:

profit[i][j] = max(profit[i][j], sell[j-1]+prices[i]-buy[j-1]) sell[j] = max(sell[j], profit[i-1][j-1]-prices[i-1]+prices[i]) buy[j] = min(buy[j], prices[i])

The time complexity of the above algorithm is O(n*k) and the space complexity is O(k).

1