Question: Find max sum in a 2D array.

This question has other variants as well:

There is a matrix with only 0's and 1's; find maximum submatrix with all 1's.
'Or'
There is a matrix with only 0's and 1's; find maximum submatrix with all 0's.
etc.

Answer: You might have heard about kadane's algorithm. This is to get the max sum in a 1-D array in O(N) time. This is based on dynamic programming approach and the approach is to traverse the array from start and get the maximum sum in part of the array traversed by that time.

Following is the code for 1D kadane algorithm.

  
void kadane(int input[], int n, int &x1, int &x2, int &max)
{
    int cur, i;
    max = 0;
    cur = 0;
    x1 = x2 = 0;
    int lx1, lx2;
    lx1 = 0;
    for(int i = 0; i<n; i++)
    {
        cur = cur+input[i];
        if(cur > max)
        {
            max = cur;
            x2 = i;
            x1 = lx1;
        }
        if (cur < 0)
        {
            cur = 0;
            lx1 = i + 1;
        }
    }
}


Now we can extend this 1D kadane algorithm to 2D kadane algorithm and can find the max sum in a N*N matrix in O(N^3).

What is needed for extending kadane algorithm is as followed:

  1. Traverse matrix at row level.
  2. have a temporary 1-D array and initialize all members as 0.
  3. For each row do following:
    •   add value in temporary array for all rows below current row (including current row)
    •   apply 1-D kadane on temporary array
    •   if your current result is greater than current maximum sum, update.
We are actually finding maximum sum sub-matrix by adding continuous rows in the original matrix and finding maximum value indexes for left and right columns.
  
#include<iostream>
using namespace std;

#define M 10
#define N 10

find_max_sum(int input[M][N])
{
    int tmp[100], n, x1, x2;
    int cur, max_sum, fx1, fx2, fy1, fy2;
    int i,j,k;
    fx1 = fx2 = fy1 = fy2 = max_sum = cur = -1;

    for (i=0; i< M; i++)
    {
        for(k=0; k<N; k++)
            tmp[k] = 0;

        for (j=i; j<M; j++)
        {
            for(k=0; k<N; k++)
                tmp[k] += input[j][k];
            kadane(tmp, N, x1, x2, cur);

            if (cur > max_sum)
            {
                fy1 = x1;
                fy2 = x2;
                fx1 = i;
                fx2 = j;
                max_sum = cur;
            }
        }
    }
    cout << "max Sum = " << max_sum << " from (" << fx1 << "," << fy1 << ") to ("
        << fx2 << "," << fy2 << ")" << endl;
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.