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

*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/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)

.

**Follow-Ups**:**Re: How to calculate largest number in sub-range?***From:*Willem

**References**:**How to calculate largest number in sub-range?***From:*Daniel Lidstrom

- Prev by Date:
**Re: How to calculate largest number in sub-range?** - Next by Date:
**Re: How much time does it need to sort 1 million random 64-bit/32-bit integers?** - Previous by thread:
**Re: How to calculate largest number in sub-range?** - Next by thread:
**Re: How to calculate largest number in sub-range?** - Index(es):