Ytukyg

I was working on a problem https://www.spoj.com/problems/LISA/

In the problem, the expression is given which has only operators (+,*). Putting brackets we need to get maximum value possible. First thing came in my mind putting brackets around + will maximize the value. But it's not working for all cases. Like in below example

 1+2*3+4*5 = (1+2)*(3+4)*5 = 105



 2*0*3+7+1*0*3 = 2*((0*3+7+1*0)*3) = 42 (  putting bracket arount not solve the problem )

Can you help me to derive the best way to put brackets around the expression?

I came across a dynamic problem way of solving the problem

f(ci,cj) = Max( f(i,j-1) operator c(i,j) , f( i+1,j-1) operator c(i,i) )



Like 3,5 =  Max of [  (3,4) * (5,5) or (3,3)+(4,5) ]

         =  Max of [   7*5  or 3+20 ] 

         =  Max of [ 35,23 ] = 35









-----------------------------------

      C1   C2   C3   C4    C5

C1     1    3    9   13    105

C2          2    6   14    70

C3               3   7     35

C4                   4     20

C5                         5

Above DP table gives correct result can someone provide proof that it gives maximum value?