@kunal patil your soln does not work for 5 3 4 5 3 3 On Tue, May 17, 2011 at 9:57 PM, Kunal Patil <kp101...@gmail.com> 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 I believe
> 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 to last
> 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 procedure till **
> 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 procedure till **
> 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 Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
<<363.gif>>
<<361.gif>>
<<33D.gif>>
<<322.gif>>
<<360.gif>>
