1. There are n balloons and each balloon has a number on it given as an array 2. You need to burst all balloons 3. When you burst a balloon balloon i you will get nums[left] * nums[i] * nums[right] coins 4. After bursting left and right elements will be adjacent 5. Burst balloons in a way that coins collected is maximised 6. Input and output is handled for you 7. It is a functional problem, please do not modify main() NOTE: left of first and right of last element is numbered 1
Input Format
Input is handled for you
Output Format
Output is handled for you
Constraints
0 <= n <= 500 0 <= array[i] <= 100
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
6 7 1 9 12 5 6
Output
1732