An interesting problem

[Matt Lawrence]

David Landgren wrote:
> 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.
>
That's a much better description of the solution I was groping for earlier.

Matt