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:

 \begin{array}{ccc} 1 & -2 & 2 \\ 5 & -3 & 5 \\ 2 & 4 & -6 \end{array}

The sub-matrix with the largest sum is:

 \begin{array}{ccc} 5 & -3 \\ 2 & 4 \end{array}

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:

       \begin{array}{ccc} 1 & -2 & 2 \\ 6 & -5 & 7 \\ 8 & -1 & 1 \end{array}

      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:

       \begin{array}{ccc} 1 & -2 & 2 \\ 5 & -3 & 5 \\ 2 & 4 & -6 \\ 6 & -5 & 7 \\ 7 & 1 & -1 \\ 8 & -1 & 1 \end{array}

      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!