@Prims:
It looks something like this:
take an array num to store:3 6 7 3 2 (sequentially as it is)
Take another array op : + * + * (sequentially as it is)
Now make a 5X5 2-D array maxResult
where maxResult[i][j] means maximum value of the subexpression form
num[i] to num[j]
Here n=5;
so u have to calculate maxResult[0][n-1]
now maxResult[i][i] will be num[i]
DP is something like this:
int calMax(i,j)
{
if there is an entry in maxResult[i][j] then return it
otherwise
{
max= -(infinity)
for(k=i;k<j;k++)
{
t1=calMax(i,k);
t2=calMax(k+1,j);
val=t1 op_k t2;
if(val>max)
max=val;
}
maxresult[i][j]=val;
return maxresult[i][j];
}
}
call
int final_max_val=calMax(0,n-1);
@juver++: Notify me if I am missing something.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
