@juver
I didnt get the approach.Could you please explain for the below
expression.
3 + 6 * 7 + 3 * 2
On Dec 20, 10:46 pm, juver++ avpostni...@gmail.com wrote:
Keep 2D arrray. For each segment (i, j) calculate min and max value for the
subexpression.
To do this, iterate k over (i, j),
@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
Result for the max[i,j] depends not only on max[k, l] but min[k,l]. E.g. for
/ operation maximum result is achived - division of max number by min
number.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
It is given in the question Given an expression E of n numbers with
*, + operations.So,I dont think that min array is required is
required in this case.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Yes, for {+,*} operations set Max state is enough.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
@juver++:
Do we need a 2-D array or 1-D array will be sufficient?
That means if I take 1-D array then max[i] will represent the maximum
value of the subexpression from 0 to i.and for i+1 we will use the
result we have got in max[i].Thus we will be able to calculate
max[N-1] which is the maximum
Keep 2D arrray. For each segment (i, j) calculate min and max value for the
subexpression.
To do this, iterate k over (i, j), check operation at k-th position and
choose the best one.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
@Pranav -
Your greedy solution fails. Sample test case - 7*0+0*7+7 :)
DP is the way to go for this.
-Swapnil
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
@juver++: gt it.thanks
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
It's a classic dynamic programming problem.
min[i][j] - minimum value for the subexpression starting at i-th position
and ending at j-th, max[i][j] - the same but stores maximum value.
Use these value to calculate value max[0][N-1], N - size of the expression.
--
You received this message
10 matches
Mail list logo
