Recently I have been solving algorithms problems for fun and thought it'd be a good idea to share some of my solutions here. So here's one called the Maxmimum Sum Problem.

### Problem

Given an $n * n$ matrix of integers, find the sum of sub-rectangular (doesn't have to be a square) matrix with the largest sum.

For example, given this matrix:

The sub-matrix with the largest sum is:

So the solution is the sum of this matrix, which is 8.

NOTE: There are actually three more sub-matrices in this example that sum to 8. Can you find them?

### Algorithm

1. Compute an $n*n$ matrix of the partial vertical sums of the input matrix. Such that $sums_{i,j} = \sum_{n=0}^{j} input_{i,n}$. For our example above, that will give us a matrix that looks like this:

This matrix can be computed in $O(n^2)$ time by adding the new row to the results of the previous row.
2. Now we can use the $sums$ we computed to find all the possible rectangles of width 1 in another matrix by subtracting rows:
Matrices of height 1:
$sums_1$
$sums_2 - sums_1$
...
$sums_{n-1} - sums_{n-2}$
$sums_n - sums_{n-1}$

Matrices of height 2:
$sums_2$
...
$sums_{n-1} - sums_{n-3}$
$sums_n - sums_{n-2}$

...

Matrices of height n-1:
$sums_{n-1}$
$sums_n - sums_{1}$

Matrices of height n:
$sums_n$

After doing each of these calculations we will have a bunch of resulting rows. In the case of our example we will end up with the following rows:

These rows can all be found in $O(n^2)$ time.

3. The numbers in the rows from step 2 represent the sums of all the possible rectangles of width 1. To find the sum of rectangles with other widths, we can sum horizontally. So we are left with a problem of finding the maximum sum consecutive sub-sequence in each row. The greatest of each of these results is the answer to the problem.The maximum sum subarray for each row can be found in $O(n)$ time by calculating the maximum sub-array that ends at each position in the row as follows:
$max_0 = row_0$
$max_i = max(row_i, max_{i-1} + row_i)$
The max-sum of the row is now the maximum value in $max$.

For example, the first row $\begin{array}{ccc} 1 & -2 & 2 \end{array}$ would produce a $max$ array of $\begin{array}{ccc} 1 & -1 & 2 \end{array}$. The maximum number in this row is 2.

And the second row $\begin{array}{ccc} 5 & -3 & 5 \end{array}$ would produce a $max$ array of $\begin{array}{ccc} 5 & 2 & 7 \end{array}$. The maximum number in this row is 7.

After we do this for all the rows we are left with $2, 7, 6, 8, 8, 8$.

Since there are $O(n^2)$ rows and the maximum sum within each row can be computed in $O(n)$ time, the complexity of this step is $O(n^3)$.

The maximum of all those values is the maximum sum of the original matrix. In our example, the largest number was 8, suggesting that the sum of the maximum-sum submatrix is 8.

The complexity of all the steps together is then $O(n^2+n^2+n^3)$, giving us a total complexity of $O(n^3)$ for the entire algorithm.

Be Sociable, Share!