Re: How to calculate largest number in subrange?
 From: Richard Heathfield <invalid@xxxxxxxxxxxxxxx>
 Date: Fri, 07 Jul 2006 07:15:20 +0000
Daniel Lidstrom said:
Hello!
I have a list of coordinates, and I want to find the largest/smallest
x/yvalue in a "subrange". For example, given these yvalues:
2, 3, 5, 3, 4, 1, 2, 1, 3
what is the largest value of values 37? This would be the largest of
5, 3, 4, 1, 2. Is it possible to precalculate some kind of structure
so that I can quickly find the largest value in any subrange,
preferrably in O(1)?
Well, yes, you can prepare an array, obviously. (Your example shows you are
using a 1based indexing system, but I'm going to hack that to 0 because
I'm more familiar with that, so I am less likely to err in a 0based
system.) In your example, it would look like this (switch to a fixedpitch
font if necessary):
Highx > 0 1 2 3 4 5 6 7 8
Lowx +
 0  2 3 5 5 5 5 5 5 5
V 1   3 5 5 5 5 5 5 5
2    5 5 5 5 5 5 5
3     3 4 4 4 4 4
4      4 4 4 4 4
5       1 2 2 3
6        2 2 3
7         1 3
8          3
int getmax(int lo, int hi, int N, int (*maxval)[N])
{
if(lo < 0  lo >= N  hi < 0  hi >= N)
{
abort(); /* be nicer than this! */
}
if(lo > hi)
{
int t = lo; lo = hi; hi = t;
}
return maxval[lo][hi];
}
which is obviously O(1).
The difficult bit is in finding shortcuts in the process of building the
array. (If you will accept O(n*n) for the arraybuilding, it's trivial.)
Clearly we can ignore the lowerleft half. Equally clearly, the main
diagonal is simply a copy of the original array. And of course each cell
after the first in any row is at least no lower than the value in the cell
directly to its left.
Anyone else take it from here?

Richard Heathfield
"Usenet is a strange place"  dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
.
 FollowUps:
 Re: How to calculate largest number in subrange?
 From: Willem
 Re: How to calculate largest number in subrange?
 References:
 How to calculate largest number in subrange?
 From: Daniel Lidstrom
 How to calculate largest number in subrange?
 Prev by Date: Re: How to calculate largest number in subrange?
 Next by Date: Re: How much time does it need to sort 1 million random 64bit/32bit integers?
 Previous by thread: Re: How to calculate largest number in subrange?
 Next by thread: Re: How to calculate largest number in subrange?
 Index(es):
Relevant Pages
