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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
