6-liner in Python


  • 0

    Gets TLE due to tuple slicing but it's nice for interviews where we have to code fast and furiously.

    class Solution(object):
        def maxCoins(self, nums):
            def max_coins(nums, memo={}):
                if nums not in memo:
                    first, last = nums[0], nums[-1]
                    memo[nums] = max([
                                     max_coins(nums[:pick + 1]) + 
                                     max_coins(nums[pick:    ]) + 
                                     first * nums[pick] * last
                                     for pick in range(1, len(nums)-1)
                                     ] or [0]
                                     )
                return memo[nums]
            return max_coins(tuple([1] + nums + [1]))
    

Log in to reply
 

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