Re: [algogeeks] Re: Largest span of Increasing Pair in an array
@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.comwrote: 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] jk. I am looking for a solution with time complexity better than O(N^2). --~--~-~--~~~---~--~~ 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.comalgogeeks%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~--- -- 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.
[algogeeks] Re: Largest span of Increasing Pair in an array
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.comwrote: 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] jk. 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Largest span of Increasing Pair in an array
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] jk.
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.comalgogeeks%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.
