68. Burst Balloons

Hard · Dynamic Programming

You have an array of balloons, each with a numeric value. You must burst all of them one by one. When you burst balloon i, you earn nums[i-1] × nums[i] × nums[i+1] coins. Balloons outside the array are treated as having value 1. Find the maximum total coins you can earn by choosing the optimal order to burst the balloons.

Input: an array of positive integers representing balloon values.

Return: the maximum coins achievable.

Examples

Example 1
Input: [3,1,5,8]
Output: 167
Explanation: Best order: burst 1, 5, 3, 8 → 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 167
Example 2
Input: [1,5]
Output: 10
Explanation: Burst 1 first (1·1·5=5), then 5 (1·5·1=5)

Constraints