582. Burst Balloons
0
Hard
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Print the maximum coins you can collect by bursting the balloons wisely.
Input Format
First Line contains size of array
Second Line contains elements of Array
Second Line contains elements of Array
Output Format
Print Maximum Coins (Integer)
Example
Input
4
3 1 5 8
Output
167
Constraints
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
1 <= n <= 300
0 <= nums[i] <= 100
Loading...
View Submissions
Console