https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/

best-time-to-buy-and-sell-stock-iv-1.py

# 188. Best Time to Buy and Sell Stock IV
# Time: O(kn**2) where n == len(price)
# Space: O(nk) 

# Time Limit Exceeded
# dp[i][j] = max(dp[i][j-1], (prices[j] - prices[m]) + dp[i-1][m]) m = 0,..,j

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0
        memo = [[0 for _ in range(len(prices))] for _ in range((k+1))]
        for i in range(1,k+1):
            for j in range(1,len(prices)):
                temp = memo[i][j-1]
                for m in range(j):
                    temp = max(temp, prices[j]-prices[m] + memo[i-1][m])
                memo[i][j] = max(memo[i][j-1], temp)
        return memo[k][len(prices)-1]

best-time-to-buy-and-sell-stock-iv-2.py

# 188. Best Time to Buy and Sell Stock IV
# Time: O(nk) where n = len(prices)
# Space: O(nk) 
'''
Memory Error!
- dp[i][j] = max(dp[i][j-1], local[i][j])
- local[i][j] = max(local[i][j-1] + diff, dp[i-1][j]+0)
where diff = prices[j] - prices[j-1]
'''
class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1:
            return 0
        
        global_profit = [[0] * len(prices) for _ in range(k+1)] 
        local_profit = [0] * len(prices)
        
        for i in range(1, k+1):
            for j in range(1, len(prices)):
                diff = prices[j] - prices[j-1]
                local_profit[j] = max(local_profit[j-1]+diff, global_profit[i-1][j-1] + max(diff, 0))
                global_profit[i][j] = max(local_profit[j], global_profit[i][j-1])
        return global_profit[-1][-1]          

best-time-to-buy-and-sell-stock-iv-3.py

# 188. Best Time to Buy and Sell Stock IV
# Time: O(nk) where n = len(prices)
# Space: O(n) 

'''
We don't really need local_profit[j], use single 
variable instead. Since localMax[j] only depend 
on local_profit[j-1], the one before.
We don't really need local_profit[j], 
For the same reason, we can one dimension array 
for the golbal_profit.
'''
# A more memory efficient version
class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if k >= len(prices)/2:
            return self.maxProfit2(k, prices)
    
        if len(prices) <= 1:
            return 0
        
        global_profit = [0] * len(prices)  
        
        for i in range(k):
            local_max = 0
            for j in range(1, len(prices)):
                diff = prices[j] - prices[j-1]
                local_max = max(local_max + diff, global_profit[j])
                global_profit[j] = max(local_max, global_profit[j-1])
           
        return global_profit[-1]
            
    def maxProfit2(self, k, prices):
        profit = 0
        for i in range(len(prices)-1):
            profit += max(0, prices[i+1] - prices[i])
        
        return profit