Practice/Google/Leetcode 312. Burst Balloons

Leetcode 312. Burst Balloons

CodingOptional

Problem

You have n balloons arranged in a row, each labeled with a number representing its value. When you pop balloon i, you earn coins equal to balloons[i-1] * balloons[i] * balloons[i+1]. After popping a balloon, the adjacent balloons become neighbors.

For balloons at the boundaries, treat out-of-bounds positions as having a value of 1. For example, popping the first balloon earns 1 * balloons[0] * balloons[1] coins.

Your task is to determine the maximum total coins you can collect by popping all the balloons in an optimal order.

Requirements

1. Return the maximum number of coins achievable by popping all balloons
2. You must pop all balloons exactly once
3. The popping order affects the total coins earned
4. Handle boundary cases correctly (treat positions outside the array as having value 1)

Constraints

• n == balloons.length
• 1 <= n <= 300
• 0 <= balloons[i] <= 100

Examples

Example 1:

` Input: balloons = [3, 1, 5, 8] Output: 167 Explanation: One optimal sequence:

• Pop balloon 1 (value 1): coins = 3 × 1 × 5 = 15
• Pop balloon 2 (value 5): coins = 3 × 5 × 8 = 120
• Pop balloon 0 (value 3): coins = 1 × 3 × 8 = 24
• Pop balloon 3 (value 8): coins = 1 × 8 × 1 = 8 Total: 15 + 120 + 24 + 8 = 167 `

Example 2:

` Input: balloons = [1, 5] Output: 10 Explanation:

• Pop balloon 0: coins = 1 × 1 × 5 = 5
• Pop balloon 1: coins = 1 × 5 × 1 = 5 Total: 10 `