Need help for the below problem....

Revision en2, by anamolous, 2022-01-18 09:50:18

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 + 1 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<=500

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English anamolous 2022-01-19 08:19:10 106
en5 English anamolous 2022-01-19 08:14:04 2 Tiny change: ':\n\n1<n<=500\n\n1<=n' -> ':\n\n1<n<=200\n\n1<=n'
en4 English anamolous 2022-01-19 08:07:41 159
en3 English anamolous 2022-01-18 09:52:37 2
en2 English anamolous 2022-01-18 09:50:18 32 Tiny change: 'e approach???\n\nTha' -> 'e approach or mention someone who can help???\n\nTha'
en1 English anamolous 2022-01-18 09:48:51 1267 Initial revision (published)