Burst Balloons

Given an integer array nums of balloon values, burst every balloon to maximize the total coins. When a balloon is burst, it earns its value multiplied by the…

Given an integer array `nums` of balloon values, burst every balloon to maximize the total coins. When a balloon is burst, it earns its value multiplied by the values of its nearest still-unburst neighbors. A missing neighbor outside the sequence has value 1. The burst balloon is removed, so later neighbors can change. Return the maximum total coins as one integer. Do not return a burst order.

- `1 <= nums.length <= 300` - `1 <= nums[i] <= 100` - Every balloon must be burst exactly once. - The visualizer accepts at most 5 balloons; longer valid inputs are execution-only.

Example 1: input nums = [3, 1, 5, 8]; output 167. Burst the value 1, then 5, then 3, then 8. The scores are 3 × 1 × 5 = 15, 3 × 5 × 8 = 120, 1 × 3 × 8 = 24, and 1 × 8 × 1 = 8, totaling 167.

Example 2: input nums = [1, 2, 3, 4]; output 40. Burst values 3, 2, 1, then 4. The live-neighbor scores are 24, 8, 4, and 4, totaling 40.

Example 3: input nums = [7]; output 7. Both outside neighbors have value 1, so the single balloon earns 1 × 7 × 1 = 7.

Category: Arrays. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.