An interesting problem

[David Landgren]

Dirk Koopman did write:

> If the area required is fixed (or otherwise determinate), I would have
> thought that doing a pass through the grid looking for the indexes of
> the largest number(s) and then doing trial solutions putting that index
> in all the positions of the area should be close.  

This doesn't work. A large (most positive) number may occur near a 
couple negatives, thus reducing its value, whereas a small patch of 
lowly positives elsewhere in the grid happen to have a larger overall sum.

I studied this algorithm at school, god, over twenty years ago. If no 
values are negative, there is only one solution: the entire matrix.

When negative values are present, one of the best heuristic solutions is 
to choose an arbitrary point and expand the region one row or column at 
a time (left, right, top or bottom) and stop when any additional 
increase in dimension results in a overall smaller sum.

As time permits, you then start over again somewhere else in the grid, 
until you consider a sufficient amount of the search space has been 
examined.

In the final step, you sort the regions by row or by column to see if 
there are any adjoining regions with the same dimensionality and 
coalesce them.