# Best Time to Buy and Sell Stock IV ###### tags `leetcode` https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/ Optimized Solution: The above solution has time complexity of O(k\*n\*n). It can be reduced if we are able to calculate maximum profit gained by selling shares on ith day in constant time. ``` profit[t][i] = max(profit [t][i-1], max(price[i] – price[j] + profit[t-1][j])) for all j in range [0, i-1] ``` If we carefully notice, ``` max(price[i] – price[j] + profit[t-1][j]) for all j in range [0, i-1] ``` can be rewritten as, ``` = price[i] + max(profit[t-1][j] – price[j]) for all j in range [0, i-1] ``` ``` = price[i] + max(prevDiff, profit[t-1][i-1] – price[i-1]) where prevDiff is max(profit[t-1][j] – price[j]) for all j in range [0, i-2] and profit[t-1][i-1] – price[i-1] is the last i-1 item ``` So, if we have already calculated max(profit[t-1][j] – price[j]) for all j in range [0, i-2], we can calculate it for j = i – 1 in constant time. In other words, we don’t have to look back in range [0, i-1] anymore to find out best day to buy. We can determine that in constant time using below revised relation. profit[t][i] = max(profit[t][i-1], price[i] + max(prevDiff, profit [t-1][i-1] – price[i-1]) where prevDiff is max(profit[t-1][j] – price[j]) for all j in range [0, i-2] Below is its optimized implementation – ```python class Solution: def maxProfit(self, k, prices): # O(k * n * n ) # def helper(tx, i, mem={}): # if i <= 0: return 0 # if i in mem: return mem[i] # not_buy = helper(tx, i-1) # buy = 0 # for j in range(0, i): # buy = max(buy ,prices[i] - prices[j] + helper(tx - 1,j)) # # comsume one transaction and solve sub-problem # mem[i] = max(not_buy, buy) # return mem[i] # return helper(k, len(prices) - 1) # Convert above to iterative way if not prices: return 0 n = len(prices) if k >= n // 2: ans = 0 for i in range(1, n): if prices[i] > prices[i - 1]: ans += prices[i] - prices[i - 1] return ans len_p = len(prices) dp = [[0 for i in range(len_p + 1)] for tx in range(2)] for tx in range(1, k+1): buy_max = -prices[0] for i in range(1, len_p): buy_max = max(buy_max, -prices[i - 1] + dp[0][i - 1]) dp[1][i] = max(dp[1][i - 1], buy_max + prices[i]) dp[0], dp[1] = dp[1], dp[0] return dp[0][len_p-1] ``` # Best Time to Buy and Sell Stock with CoolDown https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ Similar to "Best Time to Buy and Sell Stock IV", because no limitation on number of transactions, we could remove the outter loop of transaction ``` python class Solution: def maxProfit(self, prices: List[int]) -> int: # O(n^2) # def helper(i, mem={}): # if i <= 0: return 0 # if i in mem: return mem[i] # not_buy = helper(i-1) # buy = 0 # for j in range(0, i): # buy = max(buy ,prices[i] - prices[j] + helper(j-2)) # a cooldown day [buy1, cooldown, buy2] <--- distance of buy2 - buy1 = 2 # mem[i] = max(not_buy, buy) # return mem[i] # return helper(len(prices) - 1) # Convert above to iterative way if not prices: return 0 n = len(prices) dp = [0 for _ in range(n)] buy = -prices[0] for i in range(n): # for j in range(i): # prev_buy = dp[j-2] if j >= 2 else 0 # buy = max(buy, prev_buy - prices[j]) # Since j from 0 to i - 1 # This for-loop could be simplified # max(dp[0-2] - price[0]), .....,(dp[(i-1) - 2] - price[i-1]) # because the main loop is i # we can simplify buy = max(prev_buy, dp[(i-1)-2] - price[i-1]) # We have to do the boundary check if i >= 2: prev_ans = dp[(i-1)-2] if i >= 3 else 0 buy = max(prev_ans - prices[i-1], buy) prev_dp = dp[i-1] if i >= 1 else 0 dp[i] = max(prev_dp, prices[i] + buy) return dp[n-1] ```