All 6 Best Time to Buy and Sell Stock Problems Using The Same Formula

1Input: prices = [7,1,5,3,6,4]
2Output: 7
3Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
4Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
5Total profit is 4 + 3 = 7.

1Input: prices = [1,2,3,4,5]
2Output: 4
3Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
4Total profit is 4.

1Input: prices = [7,6,4,3,1]
2Output: 0
3Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 1class Solution:
 2    def maxProfit(self, prices: List[int]) -> int:
 3        # define the recursive function with memoization
 4        @lru_cache(None)
 5        def recursion(time, stock):
 6            # base case: if we have reached the end of the prices list, return 0
 7            if time >= len(prices): return 0
 8
 9            # if we don't have any stock, we can buy it
10            buy = -prices[time] + recursion(time+1, stock+1) if stock == 0 else float("-inf")
11
12            # if we have stock, we can sell it
13            sell = prices[time] + recursion(time+1, stock-1) if stock == 1 else float("-inf")
14
15            # we can also choose to hold onto the stock
16            hold = 0 + recursion(time+1, stock)
17
18            # return the maximum profit from the three options
19            return max(buy, sell, hold)
20
21        # start the recursion from time 0 and no stock
22        return recursion(0, 0)

1Input: prices = [7,1,5,3,6,4]
2Output: 5
3Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
4Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

1Input: prices = [7,6,4,3,1]
2Output: 0
3Explanation: In this case, no transactions are done and the max profit = 0.

 1class Solution:
 2    def maxProfit(self, prices):
 3        @lru_cache(None)
 4        # This is a decorator that applies memoization to the `recursion` function
 5        # so that it will only compute values for a given time and stock state once,
 6        # and then store the result in a cache so that it can be looked up later.
 7        # This helps improve the performance of the function by avoiding redundant
 8        # calculations.
 9
10        # time=idx; time indicates the curret index
11        # the current time represented by an index, the current stock state
12        # (either 0 for not having stock or 1 for having stock),
13        def recursion(time, stock, count):
14            # This is the main recursive function that computes the maximum profit
15            # possible given the current time, stock state, and count of transactions.
16
17            # If the number of transactions is greater than 1, we can't make any more
18            # transactions, so we return 0.
19            if k > 1: return 0
20
21            # If the time is greater than or equal to the length of the prices list,
22            # then we have reached the end of the prices, so we return 0.
23            if time >= len(prices): return 0
24
25            # If we don't have any stock, we can buy one at the current time and price.
26            buy = -prices[time] + recursion(time + 1, stock + 1, count) if stock == 0 else float("-inf")
27
28            # If we have stock, we can sell it at the current time and price.
29            # stock (stock = 1) to not having stock (stock = 0). Therefore,
30            # the stock value should be set to 0 in the recursive call.
31            # Since stock is currently 1, setting stock + 1 will result in a value of 0,
32            # which is the correct value for the new stock state after the sell action.
33            sell = prices[time] + recursion(time + 1, stock + 1, count+1) if stock == 1 else float("-inf")
34
35            # If we neither buy nor sell, we hold our current stock.
36            hold = 0 + recursion(time + 1, stock, count)
37
38            # Return the maximum of the three possible actions: buy, sell, or hold.
39            return max(buy, sell, hold)
40
41        # Set the maximum number of transactions to 1.
42        # day intervel is max 1
43        k = 1
44
45        # Call the `recursion` function with the initial time, stock state, and count.
46        return recursion(0, 0, 0)

1Input: prices = [3,3,5,0,0,3,1,4]
2Output: 6
3Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
4Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

1Input: prices = [1,2,3,4,5]
2Output: 4
3Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
4Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

1Input: prices = [7,6,4,3,1]
2Output: 0
3Explanation: In this case, no transaction is done, i.e. max profit = 0.

 1class Solution:
 2    def maxProfit(self, prices: List[int]) -> int:
 3        @lru_cache(None)
 4        def recursion(time, stock, count):
 5            if count >= k: return 0
 6            if time >= len(prices): return 0
 7
 8            buy = -prices[time] + recursion(time + 1, stock + 1, count) if stock == 0 else float("-inf")
 9            sell = prices[time] + recursion(time + 1, stock - 1, count+1) if stock == 1 else float("-inf")
10            hold = 0 + recursion(time + 1, stock, count)
11
12            return max(buy, sell, hold)
13
14		# day intervel is max 2
15        k = 2
16        return recursion(0, 0, 0)

1Input: k = 2, prices = [2,4,1]
2Output: 2
3Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

1Input: k = 2, prices = [3,2,6,5,0,3]
2Output: 7
3Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

 1class Solution:
 2    def maxProfit(self, k: int, prices: List[int]) -> int:
 3        @lru_cache(None)
 4        def recursion(time, stock, count):
 5
 6            if count >= k: return 0
 7            if time >= len(prices): return 0
 8
 9            buy = -prices[time] + recursion(time + 1, stock + 1, count) if stock == 0 else float("-inf")
10            sell = prices[time] + recursion(time + 1, stock - 1, count+1) if stock == 1 else float("-inf")
11            hold = 0 + recursion(time + 1, stock, count)
12
13            return max(buy, sell, hold)
14        return recursion(0, 0, 0)

1Input: prices = [1,2,3,0,2]
2Output: 3
3Explanation: transactions = [buy, sell, cooldown, buy, sell]

1Input: prices = [1]
2Output: 0

 1class Solution:
 2    def maxProfit(self, prices: List[int]) -> int:
 3        @lru_cache(None)
 4        def recursion(time, stock):
 5
 6            if time >= len(prices):
 7                return 0
 8
 9            buy = -prices[time] + recursion(time + 1, stock + 1) if stock == 0 else float("-inf")
10
11            # time + 2 is used to represent the "cool down" period that must be waited after selling a stock.
12            # In this line, the function is selling a stock and then skipping the next day (time + 1)
13            # because it is the cool down period.
14            sell = prices[time] + recursion(time + 2, stock - 1) if stock == 1 else float("-inf")
15            hold = 0 + recursion(time + 1, stock)
16
17            return max(buy, sell, hold)
18
19        return recursion(0, 0)

1Input: prices = [1,3,2,8,4,9], fee = 2
2Output: 8
3Explanation: The maximum profit can be achieved by:
4- Buying at prices[0] = 1
5- Selling at prices[3] = 8
6- Buying at prices[4] = 4
7- Selling at prices[5] = 9
8The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

1Input: prices = [1,3,7,5,10,3], fee = 3
2Output: 6

 1class Solution:
 2    def maxProfit(self, prices: List[int], fee: int) -> int:
 3        # Use lru_cache as a decorator to cache the results of the recursive function.
 4        # This will store the return values of the function using the arguments as a key,
 5        # so that if the function is called with the same arguments again,
 6        # it can return the stored value instead of recalculating it.
 7        # The parameter 'None' means that the cache has no fixed size and will continue to grow as needed.
 8        @lru_cache(None)
 9        def recursion(time, stock):
10            # base case: if we have reached the end of the prices list, return 0 profit
11            if time >= len(prices):
12                return 0
13
14            # if we don't have any stock, we can buy one
15            # the cost of buying is the price at the current time minus the profit from the next action
16            # (either selling at a later time or holding the stock)
17            buy = -prices[time] + recursion(time+1, stock+1) if stock == 0 else float("-inf")
18
19            # if we have stock, we can sell it
20            # the profit from selling is the price at the current time
21            # plus the fee for selling minus the profit from the next action
22            sell = prices[time] - fee + recursion(time+1, stock-1) if stock == 1 else float("-inf")
23
24            # if we don't want to buy or sell, we can hold on to our stock
25            # holding onto the stock means no change in profit
26            hold = 0 + recursion(time+1, stock)
27
28            # return the maximum profit of the three options
29            return max(buy, sell, hold)
30
31        # start the recursion at time 0 with no stock
32        return recursion(0,0)