Ryan Harrison
My blog, portfolio and technology related ramblings

Maximum Sum Area

19 Mar 2013

As a follow up to my previous post where we found the maximum sum subsequence of a one dimensional array, in this post the idea will be extended to cover 2d arrays or grids of numbers.

Instead of finding the subsequence of the array that contains the maximum sum, now the region of the array with the maximum sum will be found. For example in the image below, the region of the array with the largest sum is found to be enclosed by the points (1,1) and (3,2).

Here is the algorithm. Note that this is massively inefficient with an order of O(n^6) - meaning that if we double the input size, the time taken calculate the result will increase by a factor of 64 (2^6).

Here is also a small tester method displaying how the method can be used with the same 2d as shown in the example above -