Re: [algogeeks] Array problem

Terence Fri, 20 May 2011 18:25:44 -0700

Try this case:
1000 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1


On 2011-5-18 0:27, Kunal Patil wrote:

Ohh..If it is so...Sorry !!  I understood it the different way...
But if the question is as mentioned in your 2nd case then also Ibelieve there is O(n) solution.
Maintain
    two pointers: *START* and *END*
    two variables: max1 and max2
Assume arr[MAX_SIZE] to be the array containing the given elements.

Algorithm:
*1) Initially, make START point to zeroth element and END pointing tolast element of the array.
2) Calculate max1 as:
        2a) Compare arr[**START**] and arr[**END**].
                   If arr[**START**] < arr[**END**]
                      {
                         max1 = **END**- **START**;
                         Jump to 3rd step
                      }
        2b) If arr[**START**] >= arr[**END**]
                   {
**END**-- ;
jump to step 2a and repeat this proceduretill **END**!= **START*
*                   }
3) Reset **END**so that it points to last element of the array.
4) Calculate max2 as:
        4a) Compare arr[**START**] and arr[**END**].
                   If arr[**START**] < arr[**END**]
                      {
                         max2 = **END**- **START**;
                         Jump to 5th step
                      }
        4b) If arr**[START**] >= arr[**END**]
                   {
**START**++ ;
jump to step 4a and repeat this proceduretill **START**!= **END*
*                   }
5) Return max( max1, max2)*

Hope this algo is clear.
This algo makes two passes over the array. Thus it is O(2n) = O(n)..
Let me know if this algo fails for any case you can think of..
--
You received this message because you are subscribed to the GoogleGroups "Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to[email protected].For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en.


--
You received this message because you are subscribed to the Google Groups "Algorithm 
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to 
[email protected].
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

<<image/gif>>

Re: [algogeeks] Array problem

Reply via email to