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].
