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)
.



Relevant Pages

  • (patch for Bash) regex case statement
    ... Following up on my previous patch for regex conditional tests, ... /* Return an array of strings; ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
    (comp.unix.shell)
  • Re: Strategy or Iterator?
    ... It would be possible to write a class that returns the variations ... GNU General Public License for more details. ... protected CombinatoricOperator(Telements, int r) { ... An integer array backing up the original one to keep track of the ...
    (comp.lang.java.programmer)
  • (patch for Bash) regex conditional tests
    ... 'regex' are returned in array variable SUBMATCH. ... Skipping of positional parameters, array elements, string ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
    (comp.unix.shell)
  • Re: attempting an actual game...
    ... >> too great to be wasted on Tetris. ... I figured one would use a bit array as that would probably be convinient ... Using a 2D int (or, ... (I once started with typedef int Cell, with a view to making a Cell ...
    (comp.games.development.programming.misc)
  • Re: The question regarding type of pointers
    ... int day_of_year ... According to my understanding daytab is pointing to the whole daytab ... array i.e it is equivalent to p3. ... daytab is converted to a pointer to the first ...
    (comp.lang.c)