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.
