@kunal..
anuj is right..ur code works only for sorted array...and I missed the
part of doing it in O(n) time...I don't think there is way of doing it
in O(n) time...if its there and if amit knows the solution, he should
provide some hints...
On 5/16/11, anuj agarwal <coolbuddy...@gmail.com> wrote:
> Kunal,
> Your solution runs in O(n) time but it is a wrong solution. It will run fine
> if the array is sorted.
>
> Anuj Agarwal
>
> Engineering is the art of making what you want from things you can get.
>
>
> On Mon, May 16, 2011 at 7:17 PM, Kunal Patil <kp101...@gmail.com> wrote:
>
>> @Piyush Sinha: I doubt correctness of your solution. And even if it gets
>> out to be correct It is not O(n)
>> My approach:
>> Maintain 2 variables: curr_max and prev_max to keep knowledge about
>> current
>> maximum length and previous maximum length.
>>
>> Algorithm:
>>
>> *initialize curr_max and prev_max to 1
>>
>> for i=0 to size-2
>> if next element of array is greater than current element
>> {
>> increment curr_max;
>> check whether curr_max is greater than prev_max, if yes,
>> assign curr_max to prev_max;
>> }
>> else // next element is smaller than or equal to current element
>> reset curr_max to 1;
>> //End for
>>
>> Finally return prev_max*
>>
>> This is clearly O(n) as it iterates through array only once.
>>
>> --
>> 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.
>
>
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=100000655377926 *
--
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.
