@ anshu - should it not be like this :
f( x(i, n), y(j, n) ,0) = max( { x[i] * x[i+1] + max ( f( x(i+2, n), y(j, n), 0) , f( x(i+2, n), y(j, n), 1) ) }, { x[i] * y[j] + max ( f( x(i+1, n), y(j+1, n), 1 ), f( x(i+1, n), y(j +1, n), 0 ) } ); On Mon, Jul 16, 2012 at 2:15 AM, Anshu Mishra <anshumishra6...@gmail.com>wrote: > two arrays are suppose x[n], y[n]; > > take a function > f( x(i, n), y(j, n) , 0) --> taking x[i] as a first element of merged > array then max sum; > f( x(i, n), y(j, n), 1) --> taking y[j] as a first element of > merged array then max sum; > > > f( x(i, n), y(j, n) ,0) = max( { x[i] * x[i+1] + f( x(i+1, n), y(j, n), > 0) }, { x[i] * y[j] + f( x(i+1, n), y(j, n), 1 ) } ); > f( x(i, n), y(j, n) ,1) = max( { x[i] * y[j] + f( x(i, n), y(j+1, n), 0) > }, { y[j] * y[j+1] + f( x(i, n), y(j+1, n), 1 ) } ); > > final sol = max ( f( x(0, n), y(0, n) ,0), f( x(0, n), y(0, n) ,1) ); > > Now it's looking a very simple *dp *problem with O(n^2) time and space > complexity. :) > > -- > Anshuman Mishra | Software Development Engineer | Amazon > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.