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 <adol...@gmail.com> 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 <madhav...@gmail.com>:
>
>> 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 <atul.87fri...@gmail.com>
>> 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 algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>> --
>> 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 algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> 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 algogeeks+unsubscr...@googlegroups.com.
>
--
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 algogeeks+unsubscr...@googlegroups.com.
