@ Above
I think your solution would not work for A[] = {9,6,3,2,8,1}Ans is A[4]-A[1] > 0 i.e 4-1 = 3. On Tue, May 17, 2011 at 9:57 PM, Kunal Patil <[email protected]> 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 [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. > -- Amit Jaspal. Men do less than they ought, unless they do all they can -- 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.
<<363.gif>>
<<361.gif>>
<<33D.gif>>
<<322.gif>>
<<360.gif>>
