|
1 | | -# Unfinished |
2 | 1 |
|
3 | | -class Solution(object): |
| 2 | +# # My initial solution, which is wrong. |
| 3 | +# class Solution(object): |
| 4 | +# def maxProfit(self, prices): |
| 5 | +# """ |
| 6 | +# :type prices: List[int] |
| 7 | +# :rtype: int |
| 8 | +# """ |
| 9 | +# days = len(prices) |
| 10 | +# if days < 2: |
| 11 | +# return 0 |
| 12 | +# totalProfit = 0 |
| 13 | +# isCoolingDown = False |
| 14 | +# minimumPrice = prices[0] |
| 15 | +# for today in range(1, days): |
| 16 | +# if prices[today] < minimumPrice: |
| 17 | +# minimumPrice = prices[today] |
| 18 | +# isCoolingDown = False |
| 19 | +# elif minimumPrice < prices[today]: |
| 20 | +# if not isCoolingDown: |
| 21 | +# totalProfit += (prices[today] - minimumPrice) |
| 22 | +# minimumPrice = prices[today] |
| 23 | +# isCoolingDown = True |
| 24 | +# else: |
| 25 | +# isCoolingDown = False |
| 26 | +# else: |
| 27 | +# isCoolingDown = False |
| 28 | +# return totalProfit |
| 29 | + |
| 30 | + |
| 31 | +# Taken from this: https://tinyurl.com/wlol23f |
| 32 | +class Solution: |
4 | 33 | def maxProfit(self, prices): |
5 | 34 | """ |
6 | 35 | :type prices: List[int] |
7 | 36 | :rtype: int |
8 | 37 | """ |
9 | | - profit = 0 |
10 | | - cooldown = False |
11 | | - for i in range(len(prices) - 1): |
12 | | - if prices[i + 1] > prices[i] and cooldown is False: |
13 | | - profit = (prices[i + 1] - prices[i]) + profit |
14 | | - cooldown = True |
15 | | - elif prices[i + 1] > prices[i] and cooldown is True: |
16 | | - profit = (prices[i + 1] - prices[i]) + profit |
17 | | - cooldown = True |
| 38 | + if len(prices) <= 1: |
| 39 | + return 0 |
| 40 | + |
| 41 | + have_1_stock_and_sell = 'have 1 stock and sell' |
| 42 | + have_1_stock_and_keep = 'have 1 stock and keep' |
| 43 | + have_0_stock_and_buy = 'have 0 stock and buy' |
| 44 | + have_0_stock_and_rest = 'have 0 stock and rest' |
| 45 | + |
| 46 | + action_to_next_day_possible_actions = { |
| 47 | + have_1_stock_and_sell: {have_0_stock_and_rest}, # Cool-down. |
| 48 | + have_1_stock_and_keep: {have_1_stock_and_keep, have_1_stock_and_sell}, |
| 49 | + have_0_stock_and_buy: {have_1_stock_and_keep, have_1_stock_and_sell}, |
| 50 | + have_0_stock_and_rest: {have_0_stock_and_rest, have_0_stock_and_buy}, |
| 51 | + } |
| 52 | + |
| 53 | + # We initialize with the possible actions for the first day. |
| 54 | + possible_actions = [{have_0_stock_and_buy: 0, have_0_stock_and_rest: 0}] |
| 55 | + |
| 56 | + def set_max_action_to_gain(_today_actions_to_total_gain, _today_action, _previous_day_total_gain, |
| 57 | + _today_gain=0): |
| 58 | + if _today_action in _today_actions_to_total_gain: |
| 59 | + different_previous_action_today_gain = _today_actions_to_total_gain[_today_action] |
| 60 | + _today_actions_to_total_gain.update({_today_action: max(_previous_day_total_gain + _today_gain, |
| 61 | + different_previous_action_today_gain)}) |
18 | 62 | else: |
19 | | - cooldown = False |
20 | | - return profit |
| 63 | + _today_actions_to_total_gain.update({_today_action: _previous_day_total_gain + _today_gain}) |
| 64 | + |
| 65 | + # Start with the second day, compare all actions possible on the second day based on the possible actions of |
| 66 | + # the first day. |
| 67 | + i = 1 |
| 68 | + while i < len(prices): |
| 69 | + |
| 70 | + today_actions_to_total_gain = dict() |
| 71 | + today_gain = prices[i] - prices[i - 1] |
| 72 | + |
| 73 | + for previous_day_action, previous_day_total_gain in possible_actions[-1].items(): |
| 74 | + |
| 75 | + for today_action in action_to_next_day_possible_actions[previous_day_action]: |
| 76 | + |
| 77 | + if previous_day_action == have_1_stock_and_sell: |
| 78 | + # If we sold yesterday, we have to rest there, so no gain for today. |
| 79 | + set_max_action_to_gain(today_actions_to_total_gain, today_action, previous_day_total_gain) |
| 80 | + |
| 81 | + elif previous_day_action == have_1_stock_and_keep: |
| 82 | + # Whether we keep or sell, the gain is the same: |
| 83 | + set_max_action_to_gain(today_actions_to_total_gain, today_action, previous_day_total_gain, |
| 84 | + today_gain) |
| 85 | + |
| 86 | + elif previous_day_action == have_0_stock_and_buy: |
| 87 | + # In both cases, have_1_stock_and_keep and have_1_stock_and_sell would yield to the same gain: |
| 88 | + set_max_action_to_gain(today_actions_to_total_gain, today_action, previous_day_total_gain, |
| 89 | + today_gain) |
| 90 | + |
| 91 | + elif previous_day_action == have_0_stock_and_rest: |
| 92 | + # In this case, the gain is 0 because we don't hold any stock, whether we rest or buy on this |
| 93 | + # day. |
| 94 | + set_max_action_to_gain(today_actions_to_total_gain, today_action, previous_day_total_gain) |
| 95 | + |
| 96 | + possible_actions.append(today_actions_to_total_gain) |
| 97 | + i += 1 |
| 98 | + |
| 99 | + last_possible_actions = possible_actions[-1] |
| 100 | + # print('last possible actions', last_possible_actions) |
| 101 | + |
| 102 | + return max(last_possible_actions.values()) |
| 103 | + |
| 104 | + |
| 105 | + |
21 | 106 |
|
22 | 107 |
|
23 | 108 | sol = Solution() |
|
0 commit comments