Best Time to Buy and Sell Stock IV
DP on Stocks DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Best Time to Buy and Sell Stock IV (At Most K Transactions), Dynamic Programming, Memoization, Tabulation, Space Optimization, Recursion, Arrays, Time Complexity, Space Complexity, Overlapping Subproblems, Optimal Substructure, Base Cases, dynamic programming, memoization, tabulation, space optimization, recursion base case, recursion, time complexity analysis, DP State Management.
Best Time to Buy and Sell Stock IV You are given an integer array prices where prices[i] is the price of a given stock on the i th day. You are also given an integer k, which represents the maximum number of transactions you can complete. Design an algorithm to find the maximum profit you can achieve. You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Input: prices: An array of integers representing the stock prices on n days. k: An integer representing the maximum number of transactions allowed. Output: The maximum profit that can be achieved. Example: Input: prices = [3, 3, 5, 0, 0, 3, 1, 4], k = 2 Output: 6 Explanation: Buy on day 3 (price = 0) and sell on day 5 (price = 3), profit = 3 0 = 3. Then buy on day 6 (price = 1) and sell on day 7 (price = 4), profit = 4 1 = 3. Total profit = 3 + 3 = 6.