Maximize Coins from Bursting All Balloons
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Burst every balloon in some order. Bursting one earns its value times the values of its currently adjacent surviving neighbors; a missing outer neighbor contributes 1. Return the greatest total coins.
```cpp
int maxCoins(vector<int>& nums);
```
### Examples
```text
nums = [2,4] -> 12
nums = [0,3] -> 3
```
### Constraints
- There are 1 through 300 balloons.
- Values lie in [0,100].
Overview: Maximize Coins from Bursting All Balloons. Burst every balloon in some order. Bursting one earns its value times the values of its currently adjacent surviving neighbors; a missing outer neighbor contrib