Quick-n-easy 9-liner in Python using memo


  • 0

    Gets TLE because no optimizations are there but it's quick and easy to code up during an interview, so we can demonstrate the interviewer we can code something quick and fast and then move on to more sophisticated implementations of the same algorithm. Hope you like it.

    class Solution(object):
        def maxProfit(self, k, prices):
            def solve(prices, k, idx, memo={}):
                if idx <= 0 or not k: return 0
                if (k, idx) in memo: return memo[k, idx]
                nosell, sell = solve(prices, k, idx-1, memo), 0
                for i in range(idx):
                    sell = max(sell, prices[idx] - prices[i] + solve(prices, k-1, i, memo))
                memo[k, idx] = max(sell, nosell)
                return memo[k, idx]
            return solve(prices, k, len(prices) - 1)
    
    

  • 0

    This is an 8-liner that uses bottom up dp and optimizes the calc of max diff. Note the use of collections.defaultdict to handle corner cases in dp.

    class Solution(object):
        def maxProfit(self, k, prices):
            if not prices or not k: return 0
            dp, n = collections.defaultdict(int), len(prices)
            for i in range(1, k + 1):
                diff = -prices[0]
                for j in range(1, n):
                    dp[i,j] = max(dp[i,j-1], prices[j] + diff)
                    diff = max(diff, dp[i-1, j] - prices[j])
            return dp[k, n-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.