Re: How to calculate largest number in sub-range?



Daniel Lidstrom said:

Hello!

I have a list of coordinates, and I want to find the largest/smallest
x/y-value in a "sub-range". For example, given these y-values:

2, 3, 5, 3, 4, 1, 2, 1, 3

what is the largest value of values 3-7? This would be the largest of
5, 3, 4, 1, 2. Is it possible to pre-calculate some kind of structure
so that I can quickly find the largest value in any sub-range,
preferrably in O(1)?

Well, yes, you can prepare an array, obviously. (Your example shows you are
using a 1-based 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 0-based
system.) In your example, it would look like this (switch to a fixed-pitch
font if necessary):

High-x -> 0 1 2 3 4 5 6 7 8
Low-x +------------------
| 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 array-building, it's trivial.)

Clearly we can ignore the lower-left 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)
.