Hi, I think that you should convert the elements of array to positive integers, calculate the max element and add this to all elements, after you should use DP.
Thanks. Adolfo 2015-03-24 13:14 GMT-05:00 Madhav Mohan <[email protected]>: > Algo > > 1. Initialise MaxSum=0 ,I=0,n=no_of_elements > > 2. if ( n==0) > return 0 > > 3. if (n==1) > return A[0] > > 4. While(I<=n-2) > do > > // (-ve and +ve) or (-ve and -ve) > if !(A[I]>=0 && A[I+1]>=0) { > > res=findMax(A[I],A[I+1],&maxindex) //returns -1 in case both are > equal and -ve, +1 for all others > > //maxindex returns index which is greater among the two nos > if res>0 && Maxindex==I{ > MaxSum+=A[MaxIndex] > I=I+1 > else if res>0 and Maxindex=I+1{ > I+=2 > MaxSum+=A[MaxIndex] > } > else if res==-1 (Both are -ve and equal){ > MaxSum+=A[MaxIndex] > I+=2 > } > else{ > /*both are +ve*/ > MaxSum+=A[I]+A[I+1] > I=I+2 > } > > endwhile > > 4. if I==n-1{ > // if n is odd... //the execution will stop at n-1 , so we have one more > comparison with the last number... > > if MaxSum+A[I]>MaxSum > MaxSum=MaxSum+A[I] > } > > 5. Return (MaxSum) > > > I verified it extensively for test cases including your example array, > found it to output 89... > > Waiting humbly for your opinion :-) > > Thanks > Madhav > > Thanks and Regards, > Madhav Mohan > Software Engineer > Mphasis LTD,Bangalore > > > > > > On Tue, Mar 24, 2015 at 7:17 PM, atul anand <[email protected]> > wrote: > >> Given a array with +ve and -ve integer , find the maximum sum such that >> you are not allowed to skip 2 contiguous elements ( i.e you have to select >> atleast one of them to move forward). >> >> eg :- >> >> 10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3 >> >> Output : 10+20+30-10+40-1 = 89 >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
