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.
<<363.gif>>
<<361.gif>>
<<33D.gif>>
<<322.gif>>
<<360.gif>>
