Awesomely done :) +1
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.
