#312

Burst Balloons

expert · 1115 · lc hard +32 · verified · 63% accepted · 9,735 likes · top 65%

Description

You are given n balloons, indexed from 0 to n - 1, each painted with a number from the array nums. Bursting balloon i earns nums[i - 1] * nums[i] * nums[i + 1] coins. Out-of-bounds neighbors are treated as 1.

Burst all balloons in the order that maximizes your total coins. Return that maximum.

Example 1:

Input: nums = [3,1,5,8]

Output: 167

Explanation:

nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []

coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

Example 2:

Input: nums = [1,5]

Output: 10

Code

1

2

3

class Solution:
    def maxCoins(self, nums: List[int]) -> int:

class Solution:
    def maxCoins(self, nums: List[int]) -> int: