You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1] Output: 0
Constraints:
1 <= prices.length <= 50000 <= prices[i] <= 1000This approach uses dynamic programming to track three states on each day: holding, not holding with cooldown, and not holding without cooldown. The idea is to decide the best action for any day based on the previous day's states. At each step, calculate the maximum profit for holding a stock, selling it, or being idle.
This C code defines a function maxProfit that takes the array of prices and its size. The dynamic programming state variables are initialized: hold representing the maximum profit holding a stock, sell for selling it, and cooldown for the situation with a cooldown period. It iterates through each price updating these states according to whether you sell, buy, or remain idle.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of days. Each day's prices are visited once.
Space Complexity: O(1), since only a fixed amount of extra space is used.
This approach involves a recursive solution that tracks the profit by exploring all possible transactions. To optimize the solution, memoization is used to store and reuse results of repeated states to avoid redundant calculations.
This C version uses a recursive function called solve that considers each day and whether you can buy or have to sell, using memoization for repetitive states. It attempts both buying and selling actions recursively and stores maximum profits attainable to avoid recomputation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of days. Thanks to memoization, each state is computed once.
Space Complexity: O(n), for the memoization table.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the number of days. Each day's prices are visited once. |
| Recursive Approach with Memoization | Time Complexity: O(n), where n is the number of days. Thanks to memoization, each state is computed once. |
Best Time to Buy and Sell Stock with Cooldown - Leetcode 309 - Python • NeetCode • 116,170 views views
Watch 9 more video solutions →Practice Best Time to Buy and Sell Stock with Cooldown with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor