Find Max sum in a 2D array | PROGRAMMING INTERVIEWS

Find Max sum in a 2D array | PROGRAMMING INTERVIEWS

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.

In this algorithm we calculate the prefix sum for all possible row combination in O(n²) and then take out their maximum contigous sum in O(n) time. Thus doing the task in O(n³) time. 
http://www.shuatiblog.com/blog/2014/08/01/Max-Sum-In-2D-Array/

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
   1. add value in temporary array for all rows below current row
   2. apply 1-D kadane on temporary array
   3. if your current result is greater than current maximum sum, update.

public int maxSum(int[][] A) {
    int m = A.length;
    int n = A[0].length;
    int maxResult = Integer.MIN_VALUE;
    for (int i = 0; i < m; i++) {
        int[] temp = new int[n];
        for (int j = i; j < m; j++) {
            // from row#i to row#(m-1), add the number into temp[]
            for (int k = 0; k < n; k++) {
                temp[k] += A[j][k];
            }
            // find max sum for 1D array
            maxResult = Math.max(maxResult, maxSum(temp));
        }
    }
    return maxResult;
}

private int maxSum(int[] B) {
    int sumSoFar = 0;
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < B.length; i++) {
        maxSum = Math.max(maxSum, sumSoFar + B[i]);
        sumSoFar = Math.max(0, sumSoFar + B[i]);
    }
    return maxSum;
}

http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_07_-_Submatrix_with_largest_sum.jsp
from column level:
 


Basically, kadane's algorithm (complexity: O(n)) is used inside a naive maximum sum sub-array problem (complexity: O(n²)).
This gives a total complexity of O(n³)


public static double max1DSubarray(double[] array, MutableInt returnStart, MutableInt returnEnd)
{
double max_so_far = 0;
double max_ending_here = 0;

int currentStart = 0;
for (int i = 0; i < array.length; i++)
{
max_ending_here = max_ending_here + array[i];
if (max_ending_here > 0)
{
if (max_ending_here > max_so_far)
{
max_so_far = max_ending_here;
returnStart.setValue(currentStart);
returnEnd.setValue(i);
}
}
else
{
currentStart = i + 1;
max_ending_here = 0;
}
}
return max_so_far;
}
int findMaxSum (int matrix[numRows][numCols])
{
    int maxSum=0;

    for (int left = 0; left < numCols; left++)
    {
        int temp[numRows] = {0};

        for (int right = left; right < numCols; right++)
        {
            // Find sum of every mini-row between left and right columns and save it into temp[]
            for (int i = 0; i < numRows; ++i)
                temp[i] += matrix[i][right];

            // Find the maximum sum subarray in temp[].
            int sum = kadane(temp, numRows);

            if (sum > maxSum)
                maxSum = sum;
        }
    }

    return maxSum;
}

=====>
public static double max2DSubarray(double[][] array, MutableInt returnStartX, MutableInt returnStartY, MutableInt returnEndX, MutableInt returnEndY)
{
int rows = array.length, columns = array[0].length;

double max_so_far = -1, max_ending_here = 0;

for (int row1 = 0; row1 < rows; row1++)
{
double[] tmp = new double[columns];
for (int column = 0; column < columns; column++)
{
tmp[column] = 0;
}

for (int row2 = row1; row2 < rows; row2++)
{
for (int column = 0; column < columns; column++)
{
tmp[column] += array[row2][column];
}
MutableInt tmpStartY = new MutableInt(-1), tmpEndY = new MutableInt(-1);
max_ending_here = max1DSubarray(tmp, tmpStartY, tmpEndY);

if (max_ending_here > max_so_far)
{
returnStartX.setValue(row1);
returnEndX.setValue(row2);
returnStartY.setValue(tmpStartY.intValue());
returnEndY.setValue(tmpEndY.intValue());
max_so_far = max_ending_here;
}
}
}

return max_so_far;
}

1. find_max_sum(int input[M][N])  
2. {  
3.     int tmp[100], n, x1, x2;  
4.     int cur, max_sum, fx1, fx2, fy1, fy2;  
5.     int i,j,k;  
6.     fx1 = fx2 = fy1 = fy2 = max_sum = cur = -1;  
7.   
8.     for (i=0; i< M; i++)  
9.     {  
10.         for(k=0; k<N; k++)  
11.             tmp[k] = 0;  
12.   
13.         for (j=i; j<M; j++)  
14.         {  
15.             for(k=0; k<N; k++)  
16.                 tmp[k] += input[j][k];  
17.             kadane(tmp, N, x1, x2, cur);  
18.   
19.             if (cur > max_sum)  
20.             {  
21.                 fy1 = x1;  
22.                 fy2 = x2;  
23.                 fx1 = i;  
24.                 fx2 = j;  
25.                 max_sum = cur;  
26.             }  
27.         }  
28.     }  
29.     cout << "max Sum = " << max_sum << " from (" << fx1 << "," << fy1 << ") to ("  
30.         << fx2 << "," << fy2 << ")" << endl;  
31. }  

1. void kadane(int input[], int n, int &x1, int &x2, int &max)  
2. {  
3.     int cur, i;  
4.     max = 0;  
5.     cur = 0;  
6.     x1 = x2 = 0;  
7.     int lx1, lx2;  
8.     lx1 = 0;  
9.     for(int i = 0; i<n; i++)  
10.     {  
11.         cur = cur+input[i];  
12.         if(cur > max)  
13.         {  
14.             max = cur;  
15.             x2 = i;  
16.             x1 = lx1;  
17.         }  
18.         if (cur < 0)  
19.         {  
20.             cur = 0;  
21.             lx1 = i + 1;  
22.         }  
23.     }  
24. }  

http://geekmeal.blogspot.com/2013/02/syntaxhighlighter.html
https://github.com/kevindra/Problems/blob/master/array/MaxSubMatrixSum.cpp
Different solution
The trick is to apply Kadane's algorithm on a 2D matrix. We will consider all the possible 2D matrices which are starting from 0th column and treat them as 1D arrays.

int getMaxSubmatSum2(int a[][COL], int r, int c) {

  int globalmax = 0;

 

  for (int i = 0; i < r; i++)

   for (int j = i; j < r; j++) {

    int localmax = 0;

    for (int k = 0; k < c; k++) {

     localmax = max(localmax + getSubmatSum(i, k, j, k), 0);

     globalmax = max(localmax, globalmax);

    }

   }

 

  return globalmax;

 }

O(N^4)

int getMaxSubmatSum(int a[][COL], int r, int c) {

  int maxsum = 0;

  for (int r1 = 0; r1 < r; r1++) {

   for (int c1 = 0; c1 < c; c1++) {

    for (int r2 = r1; r2 < r; r2++) {

     for (int c2 = c1; c2 < c; c2++) {

      int sum = getSubmatSum(r1, c1, r2, c2);

      maxsum = max(sum, maxsum);

     }

    }

   }

  }

  return maxsum;

 }

Also check
https://plus.google.com/+JefferyYuanLifeLongProgrammer/posts/DScjK4y7iAr
http://comeoncodeon.wordpress.com/2009/04/07/maximum-subarray-in-1-d-and-2-d-array/
Read full article from Find Max sum in a 2D array | PROGRAMMING INTERVIEWS