Best Time to Buy and Sell Stock with Cooldown LeetCode solution in Python

1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3

4
        cache = {}
5

6
        def dfs(i, buying):
7

8
            if i >= len(prices):
9
                return 0
10

11
            if (i, buying) in cache:
12
                return cache[(i, buying)]
13

14
            if buying:
15
                # if have sell the share in previous step
16
                # then currently we have two options
17
                # either buy or not buy(cooldown)
18

19
                # we have bought so, increment the index and set buying flag to not buying
20
                # and don't forget that we bought so, we have to reduce that share amount from profit
21
                buy = dfs(i + 1, not buying) - prices[i]
22

23
                cooldown = dfs(i + 1, buying)
24

25
                profit = max(buy, cooldown)
26
                cache[(i, buying)] = profit
27

28
            else:
29
                # we have sell the share so,
30
                # we cannot buy next share we have to skip the next price(cooldown for one day)
31
                # set (not buying) flag to buying
32
                # we also have to add that share price to profit
33
                sell = dfs(i + 2, not buying) + prices[i]
34

35
                cooldown = dfs(i + 1, buying)
36

37
                profit = max(sell, cooldown)
38
                cache[(i, buying)] = profit
39

40
            return cache[(i, buying)]
41

42
        return dfs(0, True)