Best Time to Buy and Sell Stock III
DP on Stocks DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Best Time to Buy and Sell Stock III (at most two transactions), Arrays, Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Time Complexity, Space Complexity, Base Cases, Overlapping Subproblems, Optimal Substructure, Optimization, dynamic programming, memoization, optimization, search space optimization, tabulation, recursion, DP State Management, Stock Problems.
Best Time to Buy and Sell Stock III You are given an array prices where prices[i] is the price of a given stock on the i th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. You are allowed to complete at most two transactions. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Input Specification: An array of integers prices representing the stock prices on n days. Output Specification: A single integer, the maximum profit you can achieve. Constraints: The problem implies that the length of prices (n) will be non negative. Prices are integers. You can perform at most 2 transactions. Sample Test Case: Input: prices = [3, 3, 5, 0, 0, 3, 1, 4] Output: 6 Explanation for Sample Output: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3 0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4 1 = 3. Total profit = 3 + 3 = 6.