### anamolous's blog

By anamolous, history, 4 months ago, 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. Comments (8)
•  » » 4 months ago, # ^ | ← Rev. 3 →   sorry I don't have link for the problem as came across this problem in some hiring test.BTW, which elements you are removing in your approach as in my opinion your solution would have some extra answer than the expected.I have written the brute force to make case n=8a=[3,1,5,8,7,5,6,2]expected output: 2196code made from Your approach giving: 2286 can you please explain this testcase with your approach if I am going wrong. your approach if I am not wrongdef ans(l,r): if r<=l:return 0 tot=0 for i in range(l,r): tot=max(ans(l,i-1)+ans(i+1,r-1)+a[i-1]*a[i]*a[r]*a[r+1],tot) return tot  If mentioned this approachdef ans(l,r): if r<=l:return 0 tot=0 for i in range(l+1,r): tot=max(ans(l,i-1)+ans(i+1,r-1)+a[i-1]*a[i]*a[r]*a[r+1],tot) return tot Its not optimal as giving less answer: 2020