Let function f(idx, can_skip) be the maximum possible value when we're observing array element at idx, and can_skip tells the function whether it can skip the element it is currently observing.
The recurrence relation for f(idx, can_skip) is: 0 if idx == length of input arr, arr[idx] + f(idx+1, true) if can_skip == false, max(arr[idx] + f(idx+1, true), f(idx+1, false)) if can_skip == true The solution of the whole thing shall be: f(0, true). On Wed, Mar 25, 2015 at 2:58 PM, Coder Ad <[email protected]> wrote: > 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]. > -- 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].
