An interesting problem

[Andy Armstrong]

On 3 Jan 2007, at 20:40, McGlinchy, Alistair wrote:

>> On 3 Jan 2007, at 20:10, McGlinchy, Alistair wrote:
>>> That's sort of what I have been playing with, but it still doesn't
>>> seem
>>> impressively fast. There's a large number of off-by-one errors
>>> possible
>>> in here, but the answers seems to tally up when I check in Excel.
>>
>> Another thing you can do is have the quadtree (or whatever structure
>> you build) record the minima and maxima for each region. That'll
>> might allow you to discount some regions (too negative) without
>> having to sum them.
>
> May need a but more clarification here. How would this work for the
> following example. Consider a large matrix of -1 and +1 values with  
> this
> sub matrix in the middle
>
> -1000  -1000  -1000
> -1000  +6000  -1000
> -1000  -1000  -1000
>
> That's -2000 as a 3x3 array. But you don't want to discount it as the
> +6000 will likely be the best range alone.

If you know the minimum and maximum values in, say a 64 x 64 area of  
the array you also know the best and worst cases for any sub square  
of that area - which might allow you to avoid checking it explicitly.

I'm still thinking optimisations on a brute force approach here -  
it'd be much nicer to think of a clever algorithm - but I'm coming up  
blank and I don't think the beer's helping as much as I'd hoped :)

-- 
Andy Armstrong, hexten.net