i dnt htink a o(n) soln exists for this problem. On Wed, May 18, 2011 at 3:47 PM, amit kumar <amitthecoo...@gmail.com> wrote:
> @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>>
