while you scan the array maintain four indices plus two lengths two indices and a length mark one sub-array - start,end, length each such sub-array indicates a non-decreasing sequence, call them S1 and S2.
while one scans, S2 keeps track of incoming elements (curr sequence) S1 keeps track of the maximum length (along with indices) so far (prev sequence) as one encounters an element which is less than the previous element, this marks the end of S2, S1 replaces S2 if len S2 > len S1 else S2 starts afresh from this new element. In the end if len S2 > len S1 answer = S2 else answer = S1. PS: In the beginning and till one encounters a smaller element than the prev one for the first time, S1 = S2 On Mon, Mar 15, 2010 at 6:56 PM, Pramod Negi <[email protected]> wrote: > Hello Saurabh, > > can you explain the algo?? > > On Sun, Mar 14, 2010 at 9:55 PM, saurabh gupta <[email protected]> wrote: > >> O(N) >> >> my @a = @ARGV; >> my ($m, $j, $k, $l) = (0, 0, 0, 0); >> my $len = 0; >> my $curr = 0; >> for (my $i = 1; $i < @a; $i++) { >> if ($a[$i] >= $a[$i-1]) { >> if ($m == $k) { >> $j++; >> $l++; >> $curr++; >> $len++; >> } >> else { >> $l++; >> $curr++; >> } >> } >> else { >> if ($curr > $len) { >> $m = $k; >> $j = $l; >> $len = $curr; >> } >> $k = $l = $i; >> $curr = 0; >> } >> } >> if ($curr > $len) { >> print "$k $l"; >> } >> else { >> print "$m $j"; >> >> } >> >> >> On Sun, Mar 14, 2010 at 8:49 PM, Ralph Boland <[email protected]> wrote: >> >>> >>> On Mar 14, 7:46 am, ASHISH MISHRA <[email protected]> wrote: >>> > @ankur how u can solve it in o(n) >>> > i suppose u need atleast o(n lgn) >>> > >>> > On Sun, Sep 6, 2009 at 2:52 PM, ankur aggarwal < >>> [email protected]>wrote: >>> > >>> > > o(n) is the best sol known to me.. >>> > >>> > > On Sun, Sep 6, 2009 at 1:54 PM, Pramod Negi <[email protected]> >>> wrote: >>> > >>> > >> i guess sorting will do the work. >>> > >> any other constraint?? >>> > >>> > >> On Sun, Sep 6, 2009 at 9:52 AM, p0r$h <[email protected]> >>> wrote: >>> > >>> > >>> Given an array of integers A[N], find the maximum value of (j-k) >>> such >>> > >>> that A[k] <= A[j] & j>k. >>> > >>> I am looking for a solution with time complexity better than >>> O(N^2). >>> > >>> >>> I don't know how to solve this in the claimed O(N) time. >>> However, I have coded a data structure that, >>> given j, will find k in O(log(N)) time. >>> With it you can solve your problem in O(N log N) time. >>> The data structure is built in O(N) time and space. >>> It is part of a larger data structure that I will implement >>> and release as open source in a few months. >>> >>> Regards, >>> >>> Ralph Boland >>> >>> -- >>> 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]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. >> Says he feels all alone in a threatening world where what lies ahead is >> vague and uncertain. Doctor says "Treatment is simple. Great clown >> Pagliacci is in town tonight. Go and see him. That should pick you up." >> Man >> bursts into tears. Says "But, doctor...I am Pagliacci." >> >> -- >> 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]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says "Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up." Man bursts into tears. Says "But, doctor...I am Pagliacci." -- 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.
