Python solution: beats 98.31%


  • 0
    I
    class Solution(object):
        def maxCoins(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums = [1] + nums + [1] 
            table = [[0 for x in range(len(nums))] for y in range(len(nums))]
            # initialize solutions (table) for 3 consecutive elements
            k = 0
            while k + 2 < len(nums):
                left, right = k, k + 2
                table[left][right] = nums[k] * nums[k + 1] * nums[k + 2]
                k += 1
            for l in range(3, len(nums)):
                k = 0
                while k + l < len(nums):
                    left, right = k, k + l
                    solutions = []
                    for i in range(left + 1, right):
                        ans = table[left][i] + nums[left] * nums[i] * nums[right] + table[i][right]
                        solutions.append(ans)
                    solution = max(solutions)
                    table[left][right] = solution
                    k += 1
                l += 1
            return table[0][-1]
    
    

Log in to reply
 

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