I was trying to understand this problem Burst Balloon . Mainly selecting the most efficient balloon to burst from the given condition. Given conditions are : Below is the condition to calculate the score.
When Balloon $B_i$ Explodes then score will be a product of $B_{i-1}$ & $B_{i+1}$ (score ${}= B_{i-1}\times B_{i+1}$).
When Balloon $B_i$ Explodes and there is only left Balloon present then score will be $B_{i-1}$.
When Balloon $B_i$ Explodes and there is only right Balloon present then score will be $B_{i+1}$.
When Balloon $B_i$ explodes and there is no left and right Balloon present then score will be $B_i$.
Example:
Input: B[] = {1, 2, 3, 4}
Output: 20
Explanation:
For max score:
3 explodes, score= 4*2=8 (product of adjacent balloons)
2 explodes score= 4*1 + 8 = 12 (product of adjacent balloons)
1 explodes score= 4 + 12= 16 (only 4 is left on the left side)
4 explodes score = 4 + 16 = 20 (no balloons left so add 4)
score =20
other combinations will result in lesser scores. No sorting is allowed
But when I tried to apply this on this input n = 6 values = 7, 10, 8, 20, 50, 9.
In my opinion it should be = 1331 by using 20, 8, 10, 50, 7, 9 ballons.
I've used this nPn ways (1st balloon N ways, 2nd N-1 ways …last balloon 1 ways N*(N-1)(N-2)..2*1= N! to select balloons.
But from the geekforgeeks code this output is 1400. I'm unable to understand how can be this 1400? I know this is not pure mathematical problem because it's programming related problem.
But I'm confused how this combination is actually selected
Your last three moves are wrong. The position before these moves is $\{7,50,9\}$ and you burst $50$ scoring $63$, then $7$ scoring $9$, then $9$ scoring $9$, for $81$. But you can do better by bursting $7$ (scoring $50$) then $9$ (scoring $50$) then $50$ (scoring $50$) for $150$.
The point here is that it isn't always best to make the highest scoring move, because it may remove good options for future moves. (In other words, the greedy algorithm is not optimal.)