I have come across a problem but wasn't able to solve... Can someone help me with below problem.

You are given n balloons(n is even), 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 two adjacent(let be i,i+1) balloon, you will get nums[i — 1] * nums[i] * nums[i + 1]*nums[i + 2] coins. If i — 1 or i + 2 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.After bursting i and i+1 ,i-1 and i+2 would become adjacent.

Return the maximum coins you can collect by bursting the balloons wisely.

Constraints:

1<n<=200

1<=nums[i]<=1000

TestCase:

n=4

nums=[3,1,5,8]

Explaination remove element at index 1,2 i.e(1,5) will get score= 3 x 1 x 5 x 8 =120

array would become [3,8] removing this two would get us score= 1 x 3 x 8 x 1=24

ans=144

Similar Problem:

similar problem but with one ballon burst instead of two

I have solved the similar problem but not getting approach for the main problem.

Can someone please help me with the approach or mention someone who can help???

Thanks in Advance.

UPD: We have got the optimal (N^4/8) (thanks ShivanshJ ) approach would pass the limit thankyou man if got some optimisation even please comment below!!!