Need help for the below problem....

Правка en6, от anamolous, 2022-01-19 08:19:10

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!!!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский anamolous 2022-01-19 08:19:10 106
en5 Английский 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 Английский anamolous 2022-01-19 08:07:41 159
en3 Английский anamolous 2022-01-18 09:52:37 2
en2 Английский 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 Английский anamolous 2022-01-18 09:48:51 1267 Initial revision (published)