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 <rpbol...@gmail.com> wrote:
>
> On Mar 14, 7:46 am, ASHISH MISHRA <meetcoolash...@gmail.com> 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 <ankur.mast....@gmail.com
> >wrote:
> >
> > > o(n) is the best sol known to me..
> >
> > > On Sun, Sep 6, 2009 at 1:54 PM, Pramod Negi <negi.1...@gmail.com>
> wrote:
> >
> > >> i guess sorting will do the work.
> > >> any other constraint??
> >
> > >> On Sun, Sep 6, 2009 at 9:52 AM, p0r$h <1987.shis...@gmail.com> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@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.
