Maximize balloon shooting score

We have an array of length N
The array consists of balloons each with some points Ai
Initially our score is zero .

Whenever we shoot a balloon Ai , product of Ai-1 and Ai+1 gets added to the total score and the balloon Ai is removed from the array to form a new contiguous sequence.

If a balloon has only right of only a left neighbor, the value of that neighboring balloon is added to
the total score.
At the end when there is only one balloon left , its score is added to the total

We can choose any balloon during this process.

The goal is to maximize the score .

Sample test cases :

TC 1:
N=4
Arr= 1 2 3 4
way to get maximum score = 3->2->1->4 ( order in which balloons are shot)
Maximum score =20

TC 2:
N=5
Arr= 3 10 1 2 5
way to get maximum score = 3->1->2->5->10 ( order in which balloons are shot)
Maximum score =100

TC 3:
N=7
Arr= 12 48 28 21 67 75 85
way to get maximum score = 21->28->75->67->48->12->85 ( order in which balloons are shot)
Maximum score =16057

TC 4:
N=8
Arr=245 108 162 400 274 358 366 166
way to get maximum score = 162->108->274->358->400->366->166->245 ( order in which balloons are shot)
Maximum score =561630

@l_returns @freeloop @anon55659401

This is a dp problem , somewhat similar to matrix chain multiplication. Here are some resource to help you solve the same:



Hope this helps.
2 Likes

Thank you for the link , i will go through it