Getting the submatrix with maximum sum?

Question

Input: A 2-dimensional array NxN - Matrix - with positive and negative elements.

Output: A submatrix of any size such that its summation is the maximum among all possible submatrices.

Requirement: Algorithm complexity to be of O(N^3)

History: With the help of the Algorithmist, Larry and a modification of Kadane's Algorithm, i managed to solve the problem partly which is determining the summation only - below in Java.
Thanks to Ernesto who managed to solve the rest of the problem which is determining the boundaries of the matrix i.e. top-left, bottom-right corners - below in Ruby.

Actable

By "n-dimensional" I assume you mean 2-dimensional. N*N, not N^n. – Pul

Yes Kobi, i meant 2-dimensional (matrix), sorry for this typo. – Actable

What about the size of the submatrix? Can it be anything? – Gumbo

Yes, it could be of any size as long as it is a submatrix, could be the matrix itself, could be a vector. – Actable

This is a Dynamic Programming problem, and you can read about the O(N^3) solution at Algorithmist. – Georgiegeorgina

Thanks Larry. According to that algorithm, this should be the 1st step: int dim = matrix.length; int[][] ps = new int[dim][dim]; for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { if (j == 0) { ps[i][j] = matrix[i][j]; } else { ps[i][j] = matrix[i][j] + ps[i][j - 1]; } } } The second step is to get the n^2 combinations and apply the alg. i posted earlier on them to find the maximum. so my problem now is to find these combinations. Anyone help? – Actable

I mean each combination should be 1-dimensional array that is passed to function that compute the maximum subarray, how do i get these arrays from the matrix of partial sums? – Actable

Well, there are n^2 rows, so that's your combination. If you already have the partial sums, you can query the sum of the next column (within these rows) in O(1) time, which would be analogous to processing a single element in the traditional 1D Kadane's algorithm. – Georgiegeorgina

Did you manage to sort this out in the end and get the corners? Can you post your final code? – Church

No i didn't find a way yet to get the corners, and i didn't make any edits since then. – Actable

I found the explanation at the below link quite useful Max_Sum_SubRectange_Using_Kedane's_Algorithm – Heribertoheringer

Answer 1

About recovering the actual submatrix, and not just the maximum sum, here's what I got. Sorry I do not have time to translate my code to your java version, so I'm posting my Ruby code with some comments in the key parts

def max_contiguous_submatrix_n3(m)
  rows = m.count
  cols = rows ? m.first.count : 0

  vps = Array.new(rows)
  for i in 0..rows
    vps[i] = Array.new(cols, 0)
  end

  for j in 0...cols
    vps[0][j] = m[0][j]
    for i in 1...rows
      vps[i][j] = vps[i-1][j] + m[i][j]
    end
  end

  max = [m[0][0],0,0,0,0] # this is the result, stores [max,top,left,bottom,right]
  # these arrays are used over Kadane
  sum = Array.new(cols) # obvious sum array used in Kadane
  pos = Array.new(cols) # keeps track of the beginning position for the max subseq ending in j

  for i in 0...rows
    for k in i...rows
      # Kadane over all columns with the i..k rows
      sum.fill(0) # clean both the sum and pos arrays for the upcoming Kadane
      pos.fill(0)
      local_max = 0 # we keep track of the position of the max value over each Kadane's execution
      # notice that we do not keep track of the max value, but only its position
      sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0])
      for j in 1...cols
        value = vps[k][j] - (i==0 ? 0 : vps[i-1][j])
        if sum[j-1] > 0
          sum[j] = sum[j-1] + value
          pos[j] = pos[j-1]
        else
          sum[j] = value
          pos[j] = j
        end
        if sum[j] > sum[local_max]
          local_max = j
        end
      end
      # Kadane ends here

      # Here's the key thing
      # If the max value obtained over the past Kadane's execution is larger than
      # the current maximum, then update the max array with sum and bounds
      if sum[local_max] > max[0]
        # sum[local_max] is the new max value
        # the corresponding submatrix goes from rows i..k.
        # and from columns pos[local_max]..local_max
        # the array below contains [max_sum,top,left,bottom,right]
        max = [sum[local_max], i, pos[local_max], k, local_max]
      end
    end
  end

  return max # return the array with [max_sum,top,left,bottom,right]
end

Some notes for clarification:

I use an array to store all the values pertaining to the result for convenience. You can just use five standalone variables: max, top, left, bottom, right. It's just easier to assign in one line to the array and then the subroutine returns the array with all the needed information.

If you copy and paste this code in a text-highlight-enabled editor with Ruby support you'll obviously understand it better. Hope this helps!

Madeira

Hello Ernesto, i just saw your answer, thank you very much for effort. I'll look into your implementation shortly. – Actable

Answer 2

Here's an explanation to go with the posted code. There are two key tricks to make this work efficiently: (I) Kadane's algorithm and (II) using prefix sums. You also need to (III) apply the tricks to the matrix.

Part I: Kadane's algorithm

Kadane's algorithm is a way to find a contiguous subsequence with maximum sum. Let's start with a brute force approach for finding the max contiguous subsequence and then consider optimizing it to get Kadane's algorithm.

Suppose you have the sequence:

-1,  2,  3, -2

For the brute force approach, walk along the sequence generating all possible subsequences as shown below. Considering all possibilities, we can start, extend, or end a list with each step.

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
Possible subsequences:
-1   [sum -1]

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
Possible subsequences:
-1 (end)      [sum -1]
-1,  2        [sum  1]
 2            [sum  2]

At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
Possible subsequences:
-1, (end)       [sum -1]
-1,  2 (end)    [sum -1]
 2 (end)        [sum 2]
-1,  2,  3      [sum 4]
 2,  3          [sum 5]
 3              [sum 3]

At index 3, we consider appending the -2
-1,  2,  3, -2
             ^
Possible subsequences:
-1, (end)          [sum -1]
-1,  2 (end)       [sum  1]
 2 (end)           [sum  2]
-1,  2  3 (end)    [sum  4]
 2,  3 (end)       [sum  5]
 3, (end)          [sum  3]
-1,  2,  3, -2     [sum  2]
 2,  3, -2         [sum  3]
 3, -2             [sum  1]
-2                 [sum -2]

For this brute force approach, we finally pick the list with the best sum, (2, 3), and that's the answer. However, to make this efficient, consider that you really don't need to keep every one of the lists. Out of the lists that have not ended, you only need to keep the best one, the others cannot do any better. Out of the lists that have ended, you only might need to keep the best one, and only if it's better than ones that have not ended.

So, you can keep track of what you need with just a position array and a sum array. The position array is defined like this: position[r] = s keeps track of the list which ends at r and starts at s. And, sum[r] gives a sum for the subsequence ending at index r. This is optimized approach is Kadane's algorithm.

Running through the example again keeping track of our progress this way:

At index 0, we consider appending the -1
-1,  2,  3, -2
 ^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1

At index 1, we consider appending the 2
-1,  2,  3, -2
     ^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2


At index 2, we consider appending the 3
-1,  2,  3, -2
         ^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5

Again, we choose to extend because that gives a higher sum that starting a new one.
-1,  2,  3, -2
             ^
position[0] = 0      sum[0] = -1
position[1] = 1      sum[1] = 2
position[2] = 1      sum[2] = 5
positions[3] = 3     sum[3] = 3

Again, the best sum is 5 and the list is from index 1 to index 2, which is (2, 3).

Part II: Prefix sums

We want to have a way to compute the sum along a row, for any start point to any endpoint. I want to compute that sum in O(1) time rather than just adding, which takes O(m) time where m is the number of elements in the sum. With some precomputing, this can be achieved. Here's how. Suppose you have a matrix:

a   d   g
b   e   h 
c   f   i

You can precompute this matrix:

a      d      g
a+b    d+e    g+h
a+b+c  d+e+f  g+h+i

Once that is done you can get the sum running along any column from any start to endpoint in the column just by subtracting two values.

Part III: Bringing tricks together to find the max submatrix

Assume that you know the top and bottom row of the max submatrix. You could do this:

1. Ignore rows above your top row and ignore rows below your bottom row.
2. With what matrix remains, consider the using sum of each column to form a sequence (sort of like a row that represents multiple rows). (You can compute any element of this sequence rapidly with the prefix sums approach.)
3. Use Kadane's approach to figure out best subsequence in this sequence. The indexes you get will tell you the left and right positions of the best submatrix.

Now, what about actually figuring out the top and bottom row? Just try all possibilities. Try putting the top anywhere you can and putting the bottom anywhere you can, and run the Kadane-base procedure described previously for every possibility. When you find a max, you keep track of the top and bottom position.

Finding the row and column takes O(M^2) where M is the number of rows. Finding the column takes O(N) time where N is the number of columns. So total time is O(M^2 * N). And, if M=N, the time required is O(N^3).

Antisepsis

Hi, Nice explanation, however, please clarify the following line in Part 2 - Prefix Sum - "Once that is done you can get the sum running along any column from from any start to end point in the column just by subtracting two values." I understood that we can get sum between any two colums by subtracting a pair of values in the new matrix.. but how to do that pair..?? Or I'm getting it wrong..?? – Amersham

The prefix sum trick is a cool idea! Just be sure that in problems of scale you don't overflow whatever data type you're using by adding so much! – Contemplative

Your Kadane's explanation is really good. But I feel in the last line of your explanation, this "positions[3] = 3 sum[3] = 3" should be actually this -> "position[3] = 1 sum[3] = 3". This is because sum is obtained by adding to the previous sum, and not by that element itself. Hence the starting position should remain as 1 for the index 3. – Fokos

Answer 3

There are already plenty of answers, but here is another Java implementation I wrote. It compares 3 solutions:

1. Naïve (brute force) - O(n^6) time
2. The obvious DP solution - O(n^4) time and O(n^3) space
3. The more clever DP solution based on Kadane's algorithm - O(n^3) time and O(n^2) space

There are sample runs for n = 10 thru n = 70 in increments of 10 with a nice output comparing run time and space requirements.

Code:

public class MaxSubarray2D {

    static int LENGTH;
    final static int MAX_VAL = 10;

    public static void main(String[] args) {

        for (int i = 10; i <= 70; i += 10) {
            LENGTH = i;

            int[][] a = new int[LENGTH][LENGTH];

            for (int row = 0; row < LENGTH; row++) {
                for (int col = 0; col < LENGTH; col++) {
                    a[row][col] = (int) (Math.random() * (MAX_VAL + 1));
                    if (Math.random() > 0.5D) {
                        a[row][col] = -a[row][col];
                    }
                    //System.out.printf("%4d", a[row][col]);
                }
                //System.out.println();
            }
            System.out.println("N = " + LENGTH);
            System.out.println("-------");

            long start, end;
            start = System.currentTimeMillis();
            naiveSolution(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   no auxiliary space requirements");
            start = System.currentTimeMillis();
            dynamicProgammingSolution(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   requires auxiliary space for "
                    + ((int) Math.pow(LENGTH, 4)) + " integers");
            start = System.currentTimeMillis();
            kadane2D(a);
            end = System.currentTimeMillis();
            System.out.println("   run time: " + (end - start) + " ms   requires auxiliary space for " +
                    + ((int) Math.pow(LENGTH, 2)) + " integers");
            System.out.println();
            System.out.println();
        }
    }

    // O(N^2) !!!
    public static void kadane2D(int[][] a) {
        int[][] s = new int[LENGTH + 1][LENGTH]; // [ending row][sum from row zero to ending row] (rows 1-indexed!)
        for (int r = 0; r < LENGTH + 1; r++) {
            for (int c = 0; c < LENGTH; c++) {
                s[r][c] = 0;
            }
        }
        for (int r = 1; r < LENGTH + 1; r++) {
            for (int c = 0; c < LENGTH; c++) {
                s[r][c] = s[r - 1][c] + a[r - 1][c];
            }
        }
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;
        for (int r1 = 1; r1 < LENGTH + 1; r1++) { // rows 1-indexed!
            for (int r2 = r1; r2 < LENGTH + 1; r2++) { // rows 1-indexed!
                int[] s1 = new int[LENGTH];
                for (int c = 0; c < LENGTH; c++) {
                    s1[c] = s[r2][c] - s[r1 - 1][c];
                }
                int max = 0;
                int c1 = 0;
                for (int c = 0; c < LENGTH; c++) {
                    max = s1[c] + max;
                    if (max <= 0) {
                        max = 0;
                        c1 = c + 1;
                    }
                    if (max > maxSum) {
                        maxSum = max;
                        maxRowStart = r1 - 1;
                        maxColStart = c1;
                        maxRowEnd = r2 - 1;
                        maxColEnd = c;
                    }
                }
            }
        }

        System.out.print("KADANE SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }

    // O(N^4) !!!
    public static void dynamicProgammingSolution(int[][] a) {
        int[][][][] dynTable = new int[LENGTH][LENGTH][LENGTH + 1][LENGTH + 1]; // [row][col][height][width]
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 0; h < LENGTH + 1; h++) {
                    for (int w = 0; w < LENGTH + 1; w++) {
                        dynTable[r][c][h][w] = 0;
                    }
                }
            }
        }

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 1; h <= LENGTH - r; h++) {
                    int rowTotal = 0;
                    for (int w = 1; w <= LENGTH - c; w++) {
                        rowTotal += a[r + h - 1][c + w - 1];
                        dynTable[r][c][h][w] = rowTotal + dynTable[r][c][h - 1][w];
                    }
                }
            }
        }

        for (int r = 0; r < LENGTH; r++) {
            for (int c = 0; c < LENGTH; c++) {
                for (int h = 0; h < LENGTH + 1; h++) {
                    for (int w = 0; w < LENGTH + 1; w++) {
                        if (dynTable[r][c][h][w] > maxSum) {
                            maxSum = dynTable[r][c][h][w];
                            maxRowStart = r;
                            maxColStart = c;
                            maxRowEnd = r + h - 1;
                            maxColEnd = c + w - 1;
                        }
                    }
                }
            }
        }

        System.out.print("    DP SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }


    // O(N^6) !!!
    public static void naiveSolution(int[][] a) {
        int maxSum = Integer.MIN_VALUE;
        int maxRowStart = -1;
        int maxColStart = -1;
        int maxRowEnd = -1;
        int maxColEnd = -1;

        for (int rowStart = 0; rowStart < LENGTH; rowStart++) {
            for (int colStart = 0; colStart < LENGTH; colStart++) {
                for (int rowEnd = 0; rowEnd < LENGTH; rowEnd++) {
                    for (int colEnd = 0; colEnd < LENGTH; colEnd++) {
                        int sum = 0;
                        for (int row = rowStart; row <= rowEnd; row++) {
                            for (int col = colStart; col <= colEnd; col++) {
                                sum += a[row][col];
                            }
                        }
                        if (sum > maxSum) {
                            maxSum = sum;
                            maxRowStart = rowStart;
                            maxColStart = colStart;
                            maxRowEnd = rowEnd;
                            maxColEnd = colEnd;
                        }
                    }
                }
            }
        }

        System.out.print(" NAIVE SOLUTION |   Max sum: " + maxSum);
        System.out.print("   Start: (" + maxRowStart + ", " + maxColStart +
                ")   End: (" + maxRowEnd + ", " + maxColEnd + ")");
    }

}

Carder

Answer 4

Here is a Java version of Ernesto implementation with some modifications:

public int[][] findMaximumSubMatrix(int[][] matrix){
    int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }
    
    int maxSum = matrix[0][0];
    int top = 0, left = 0, bottom = 0, right = 0; 
    
    //Auxiliary variables 
    int[] sum = new int[dim];
    int[] pos = new int[dim];
    int localMax;                        

    for (int i = 0; i < dim; i++) {
        for (int k = i; k < dim; k++) {
            // Kadane over all columns with the i..k rows
            reset(sum);
            reset(pos);
            localMax = 0;
            //we keep track of the position of the max value over each Kadane's execution
            // notice that we do not keep track of the max value, but only its position
            sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]);
            for (int j = 1; j < dim; j++) {                    
                if (sum[j-1] > 0){
                    sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
                    pos[j] = pos[j-1];
                }else{
                    sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]);
                    pos[j] = j;
                }
                if (sum[j] > sum[localMax]){
                    localMax = j;
                }
            }//Kadane ends here
            
            if (sum[localMax] > maxSum){
                  /* sum[localMax] is the new max value
                    the corresponding submatrix goes from rows i..k.
                     and from columns pos[localMax]..localMax
                     */
                maxSum = sum[localMax];
                top = i;
                left = pos[localMax];
                bottom = k;
                right = localMax;
            }      
        }
    }
    System.out.println("Max SubMatrix determinant = " + maxSum);
    //composing the required matrix
    int[][] output = new int[bottom - top + 1][right - left + 1];
    for(int i = top, k = 0; i <= bottom; i++, k++){
        for(int j = left, l = 0; j <= right ; j++, l++){                
            output[k][l] = matrix[i][j];
        }
    }
    return output;
}

private void reset(int[] a) {
    for (int index = 0; index < a.length; index++) {
        a[index] = 0;
    }
}

Actable

Answer 5

With the help of the Algorithmist and Larry and a modification of Kadane's Algorithm, here is my solution:

int dim = matrix.length;
    //computing the vertical prefix sum for columns
    int[][] ps = new int[dim][dim];
    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) {
            if (j == 0) {
                ps[j][i] = matrix[j][i];
            } else {
                ps[j][i] = matrix[j][i] + ps[j - 1][i];
            }
        }
    }
    int maxSoFar = 0;
    int min , subMatrix;
    //iterate over the possible combinations applying Kadane's Alg.
    for (int i = 0; i < dim; i++) {
        for (int j = i; j < dim; j++) {
            min = 0;
            subMatrix = 0;
            for (int k = 0; k < dim; k++) {
                if (i == 0) {
                    subMatrix += ps[j][k];
                } else {
                    subMatrix += ps[j][k] - ps[i - 1 ][k];
                }
                if(subMatrix < min){
                    min = subMatrix;
                }
                if((subMatrix - min) > maxSoFar){
                    maxSoFar = subMatrix - min;
                }                    
            }
        }
    }

The only thing left is to determine the submatrix elements, i.e: the top left and the bottom right corner of the submatrix. Anyone suggestion?

Actable

Just keep track of it in your if statements. By the way, it's probably better to edit your original question as opposed to submitting an answer. – Georgiegeorgina

I managed to do this in the 1-dimensional problem: for (int i = 0; i < a.length; i++) { subArray += a[i]; if(subArray < min){ offset = i+1; min = subArray; } if((subArray - min) > best){ length ++; best = subArray - min; } } But i had some problems in the matrix case. Excuse me being newbie here, i don't know what is best. – Actable

Well, if you store an offset variable, you would already know i, j, and k, so you can figure out the corners of the submatrix from that. – Georgiegeorgina

Thanks Larry for your help. I know that this is what i should do but the problem is i can't determine where the offset will be knowing the "min" element coordinates, also how to apply the length value to find the right corner. – Actable

Answer 6

this is my implementation of 2D Kadane algorithm. I think it is more clear. The concept is based on just kadane algorithm. The first and second loop of the main part (that is in the bottom of the code) is to pick every combination of the rows and 3rd loop is to use 1D kadane algorithm by every following column sum (that can be computed in const time because of preprocessing of matrix by subtracting values from two picked (from combintation) rows). Here is the code:

    int [][] m = {
            {1,-5,-5},
            {1,3,-5},
            {1,3,-5}
    };
    int N = m.length;

    // summing columns to be able to count sum between two rows in some column in const time
    for (int i=0; i<N; ++i)
        m[0][i] = m[0][i];
    for (int j=1; j<N; ++j)
        for (int i=0; i<N; ++i)
            m[j][i] = m[j][i] + m[j-1][i];

    int total_max = 0, sum;
    for (int i=0; i<N; ++i) {
        for (int k=i; k<N; ++k) { //for each combination of rows
            sum = 0;
            for (int j=0; j<N; j++) {       //kadane algorithm for every column
                sum += i==0 ? m[k][j] : m[k][j] - m[i-1][j]; //for first upper row is exception
                total_max = Math.max(sum, total_max);
            }
        }
    }

    System.out.println(total_max);

Sandon

Answer 7

I am going to post an answer here and can add actual c++ code if it is requested because I had recently worked through this. Some rumors of a divide and conqueror that can solve this in O(N^2) are out there but I haven't seen any code to support this. In my experience the following is what I have found.

    O(i^3j^3) -- naive brute force method
    o(i^2j^2) -- dynamic programming with memoization
    O(i^2j)   -- using max contiguous sub sequence for an array


if ( i == j ) 
O(n^6) -- naive
O(n^4) -- dynamic programming 
O(n^3) -- max contiguous sub sequence

Procrustes

Answer 8

Have a look at JAMA package; I believe it will make your life easier.

Cenozoic

Thanks Anax. It is a useful package and i've never heard about it, but i think i need to use standard API, it is kinda algorithm problem. – Actable

Answer 9

Here is the C# solution. Ref: http://www.algorithmist.com/index.php/UVa_108

public static MaxSumMatrix FindMaxSumSubmatrix(int[,] inMtrx)
{
    MaxSumMatrix maxSumMtrx = new MaxSumMatrix();

    // Step 1. Create SumMatrix - do the cumulative columnar summation 
    // S[i,j] = S[i-1,j]+ inMtrx[i-1,j];
    int m = inMtrx.GetUpperBound(0) + 2;
    int n = inMtrx.GetUpperBound(1)+1;
    int[,] sumMatrix = new int[m, n];

    for (int i = 1; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            sumMatrix[i, j] = sumMatrix[i - 1, j] + inMtrx[i - 1, j];
        }
    }

    PrintMatrix(sumMatrix);

    // Step 2. Create rowSpans starting each rowIdx. For these row spans, create a 1-D array r_ij            
    for (int x = 0; x < n; x++)
    {
        for (int y = x; y < n; y++)
        {
            int[] r_ij = new int[n];

            for (int k = 0; k < n; k++)
            {
                r_ij[k] = sumMatrix[y + 1,k] - sumMatrix[x, k];
            }

            // Step 3. Find MaxSubarray of this r_ij. If the sum is greater than the last recorded sum =>
            //          capture Sum, colStartIdx, ColEndIdx.
            //          capture current x as rowTopIdx, y as rowBottomIdx.
            MaxSum currMaxSum = KadanesAlgo.FindMaxSumSubarray(r_ij);

            if (currMaxSum.maxSum > maxSumMtrx.sum)
            {
                maxSumMtrx.sum = currMaxSum.maxSum;
                maxSumMtrx.colStart = currMaxSum.maxStartIdx;
                maxSumMtrx.colEnd = currMaxSum.maxEndIdx;
                maxSumMtrx.rowStart = x;
                maxSumMtrx.rowEnd = y;
            }
        }
    }

    return maxSumMtrx;
}

public static void PrintMatrix(int[,] matrix)
{
    int endRow = matrix.GetUpperBound(0);
    int endCol = matrix.GetUpperBound(1);
    PrintMatrix(matrix, 0, endRow, 0, endCol);
}

public static void PrintMatrix(int[,] matrix, int startRow, int endRow, int startCol, int endCol)
{
    StringBuilder sb = new StringBuilder();
    for (int i = startRow; i <= endRow; i++)
    {
        sb.Append(Environment.NewLine);
        for (int j = startCol; j <= endCol; j++)
        {
            sb.Append(string.Format("{0}  ", matrix[i,j]));
        }
    }

    Console.WriteLine(sb.ToString());
}

// Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum
public static MaxSum FindMaxSumSubarray(int[] inArr)
{
    int currMax = 0;
    int currStartIndex = 0;
    // initialize maxSum to -infinity, maxStart and maxEnd idx to 0.

    MaxSum mx = new MaxSum(int.MinValue, 0, 0);

    // travers through the array
    for (int currEndIndex = 0; currEndIndex < inArr.Length; currEndIndex++)
    {
        // add element value to the current max.
        currMax += inArr[currEndIndex];

        // if current max is more that the last maxSum calculated, set the maxSum and its idx
        if (currMax > mx.maxSum)
        {
            mx.maxSum = currMax;
            mx.maxStartIdx = currStartIndex;
            mx.maxEndIdx = currEndIndex;
        }

        if (currMax < 0) // if currMax is -ve, change it back to 0
        {
            currMax = 0;
            currStartIndex = currEndIndex + 1;
        }
    }

    return mx;
}

struct MaxSum
{
    public int maxSum;
    public int maxStartIdx;
    public int maxEndIdx;

    public MaxSum(int mxSum, int mxStart, int mxEnd)
    {
        this.maxSum = mxSum;
        this.maxStartIdx = mxStart;
        this.maxEndIdx = mxEnd;
    }
}

class MaxSumMatrix
{
    public int sum = int.MinValue;
    public int rowStart = -1;
    public int rowEnd = -1;
    public int colStart = -1;
    public int colEnd = -1;
}

Officiate

Answer 10

Here is my solution. It's O(n^3) in time and O(n^2) space. https://gist.github.com/toliuweijing/6097144

// 0th O(n) on all candidate bottoms @B.
// 1th O(n) on candidate tops @T.
// 2th O(n) on finding the maximum @left/@right match.
int maxRect(vector<vector<int> >& mat) {
    int n               = mat.size();
    vector<vector<int> >& colSum = mat;

    for (int i = 1 ; i < n ; ++i) 
    for (int j = 0 ; j < n ; ++j)
        colSum[i][j] += colSum[i-1][j];

    int optrect = 0;
    for (int b = 0 ; b < n ; ++b) {
        for (int t = 0 ; t <= b ; ++t) {
            int minLeft = 0;
            int rowSum[n];
            for (int i = 0 ; i < n ; ++i) {
                int col = t == 0 ? colSum[b][i] : colSum[b][i] - colSum[t-1][i];
                rowSum[i] = i == 0? col : col + rowSum[i-1];
                optrect = max(optrect, rowSum[i] - minLeft); 
                minLeft = min(minLeft, rowSum[i]);
            }
        }
    }

    return optrect;
}

Valeric

Answer 11

I would just parse the NxN array removing the -ves whatever remains is the highest sum of a sub matrix.

The question doesn't say you have to leave the original matrix intact or that the order matters.

Ekaterinburg

Can you add more... substance to your post? – Macdougall