All problems

Burst Balloons

Hard · dynamic programming

A row of lanterns hangs along a wall, and glow[i] is how brightly lantern i shines. You put the lanterns out one at a time, in any order you like, until none are left.

Each time you put one out, you score the product of three numbers: the glow of the nearest lantern still lit on its left, its own glow, and the glow of the nearest lantern still lit on its right. If there is no lit lantern on one side, that side counts as 1.

Return the largest total score you can get by choosing the order well.

Examples

Example 1

Input: glow = [2, 3, 4]

Output: 36

Put out the 3 first (2 x 3 x 4 = 24), then the 2 (1 x 2 x 4 = 8), then the 4 (1 x 4 x 1 = 4). Total 36, and no other order does better.

Example 2

Input: glow = [5]

Output: 5

There is only one lantern, with nothing lit on either side: 1 x 5 x 1 = 5.

Example 3

Input: glow = [4, 0, 3]

Output: 16

Put out the 0 first (4 x 0 x 3 = 0), then the 3 (4 x 3 x 1 = 12), then the 4 (1 x 4 x 1 = 4). Total 16.

Constraints