@Prakhar Jain
I believe that the following recurrence shall solve it..
Take an array C[n+1][n+1]...
Now, we only need to calculate those C[i][j]'s where i+j is even..
// Assuming 1-based index...
Initialization condition...
C[0][0]=0;
for(int i =0; i =n; i+=2)
{
C[0][i] = C[0][i-2] +
@small correction:
In the initialization condition the loop index i shall start from 2
and not 0..
// for(int i =2; i =n; i+=2)
On 30 July, 15:23, Lucifer sourabhd2...@gmail.com wrote:
@Prakhar Jain
I believe that the following recurrence shall solve it..
Take an array C[n+1][n+1]...
@vivek..
u can't sort.. its a stable merge...
The question is to stably merge the two arrays..the stable merge of
the 2 arrays can take place in (2n C n) ways.. 1 of these arrangements
will lead to the maximum sum..
We are required to find that sequence/maxsum..
A stable merge in this case is
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1280183627
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
@ 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
Awesomely done :) +1
On Mon, Jul 16, 2012 at 2:15 AM, Anshu Mishra anshumishra6...@gmail.comwrote:
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
Please see *stable merge *in question.
On Sun, Jul 15, 2012 at 2:04 AM, sengar.mahi sengar.m...@gmail.com wrote:
@naveen : 3*7+2*9+1*3 =42 is not maximum..
sum of the product would me maximum wen, i guess, most weighted elements
are adjacent
like in this case
if c={1,2,3,3,7,9}
1*2 + 3*3 +
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),
As the final array contains element in stable-order, at any time we have 3
options for choosing the elements from A B.
1- A[i] A[i+1]
2- A[i] B[I]
3- B[i] B[i+1]
we will choose that pair whose product is maximum.
For ex:-
A-2,1,3
B-3,7,9
C- 3,7,2,9,1,3
Its a linear time solution with
@naveen : 3*7+2*9+1*3 =42 is not maximum..
sum of the product would me maximum wen, i guess, most weighted elements
are adjacent
like in this case
if c={1,2,3,3,7,9}
1*2 + 3*3 + 7*9=74 (maximum )
thus this question is just merging both strings such resultant (here C) is
in sorted order which can
O(n2) Time and O(n2) space solution -
1. Total of (n2 + 2n - 2) products possible with given combinations - (n -
1) times (n + 1) and once n for the first array for the last element; total
of (n -1) products for 2nd array -therefore (n -1)(n +1) + n + (n-1) = n2
+ 2n - 2. Products to be
11 matches
Mail list logo
