@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 nothing but interleaved arrangement of
the 2 arrays..
for ex-
A= { a1, a2, a3}
B= { b1, b2, b3}
Stable merges:
------------------
C = { a1,b1,a2,b2,b3,a3}
or say,
C = { b1,a1,a2,b2,a3,b3}
The above array is formed by stable merge because the order of 'a's
and 'b's in the merged array is intact..
i.e a1 comes before a2 which in turn comes before a3 .. same goes for
b1,b2,b3..
Unstable merge:
--------------------
C = { a2,b1,a1,b2,b3,a3}
// here a2 is placed before a1.. hence not stable...
On 30 July, 19:56, vivek veldandi <vivek.veldandi...@gmail.com> wrote:
> On Mon, Jul 30, 2012 at 3:56 PM, Lucifer <sourabhd2...@gmail.com> wrote:
> > @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]...
>
> > > 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] + B[i] * B[i-1];}
>
> > > for(int i =0; i <=n; i+=2)
> > > {
> > > C[i][0] = C[i-2][0] + A[i] * A[i-1];
>
> > > }
>
> > > Calculating the values of C..
> > > for(int i =1; i <=n; ++i)
> > > for(int j =1; j <=n; ++j)
> > > {
> > > if( (i+j)%2 = 0 )
> > > {
> > > C[i][j] = max {
> > > C[i-2][j] + A[i-1] * A[i] , // if(i-2 >=0)
> > > C[i-1][j-1] + A[i] * B[j] , // if(i-1 >=0 &&
> > > j-1 >=0)
> > > C[i][j-2] + B[i-1] * B[i] // if( j-2 >=0)
> > > } ;
> > > }
> > > }
>
> > > Answer : Maximum value - C[n][n]
>
> > > On 10 July, 08:13, Prakhar Jain <jprakha...@gmail.com> wrote:
>
> > > > You are given 2 arrays of size 'n' each. You need to stable-merge these
> > > > arrays such that in the new array sum of product of consecutive
> > elements is
> > > > maximized.
> > > > eg
> > > > A= { 2, 1, 3}
> > > > B= { 3, 7, 9}
> > > > Stable merging A and B will give an array C with '2n' elements say
> > C={c1,
> > > > c2, c3, c4, c5, c6}
> > > > You need to find a new array C by merging (stable) A and B such that
> > sum=
> > > > c1*c2 + c3*c4 + c5* c6..... n terms is maximum.
>
> > > > --
> > > > Prakhar Jain
> > > > IIIT Allahabad
> > > > B.Tech IT 3rd Year
> > > > Mob no: +91 9454992196
> > > > E-mail: rit2009...@iiita.ac.in
> > > > jprakha...@gmail.com
>
> > --
> > 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.
>
> > sort them and merge..u will get max in all cases
--
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.
