Best Time to Buy and Sell Stock with Cooldown
DP on Stocks DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Maximizing Stock Trading Profit with Cooldown using Dynamic Programming, Arrays, Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Time Complexity, Space Complexity, Overlapping Subproblems, Optimal Substructure, Base Cases, Optimization, constraints, dynamic programming, space complexity, memoization, state management, tabulation, space optimization, recursion, time complexity analysis, DP State Management, Stock Problems.
Stock Buy and Sell with Cooldown Problem Statement 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 completing as many transactions as possible (buy one and sell one share of the stock). You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). However, there is a cooldown period after you sell a stock: you cannot buy stock on the next day (i.e., if you sell on day i, you can only buy on day i + 2 or later). Return the maximum profit you can achieve. Input Specification The first line contains an integer n, the number of days. The second line contains n space separated integers, prices[0], prices[1], ..., prices[n 1], representing the stock prices on each day. Output Specification Return a single integer, the maximum profit that can be generated. Constraints 1 <= n <= 10^5 0 <= prices[i] <= 1000 Sample Test Case Input: Output: Explanation: 1. Buy on day 0 (price = 4), Sell on day 1 (price = 9). Profit = 9 4 = 5. 2. Cooldown on day 2. 3. Buy on day 3 (price = 4), Sell on day 4 (price = 10). Profit = 10 4 = 6. Total Maximum Profit = 5 + 6 = 11.