Maximum Sum Rectangle

Problem Statement

Given a 2D matrix, find the largest possible sum submatrix in it and print its value.

Submatrix: In this problem, a submatrix is defined as a rectangle, which can be obtained by deleting a certain number of boundary rows and columns from the given original matrix. All elements of the rectangle need to be contiguous either row-wise or column-wise.

Sample Test Cases :

Input 1:
Matrix =
{{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}}

Output 1:
(top, left) : (1, 1)
(bottom, right) : (3, 3)
29
Explanation 1:

We can observe from the image that the shaded submatrix denotes the maximum sum rectangle in the above example. The sum of elements in this submatrix gives us a value of 29.

Input 2:
Matrix =
{{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0},
{1, 0, 1, 0, 1},
{0, 1, 0, 1, 0}}

Output 2:
(top, left) : (0, 0)
(bottom, right) : (3, 4)
10
Explanation 2: The entire matrix will correspond to the maximum sum rectangle for this matrix.

Naive Approach

The naive approach is to iterate over all the submatrices of the matrix and calculate the maximum rectangle sum over all the submatrices. We will use 4 nested loops to fix the corners of the rectangle/submatrix, and then another 2 nested loops to calculate the sum of that submatrix.

C++ Implementation

void maxMatrixSum(vector < vector < int >> & matrix) {
  int n = matrix.size();
  int m = matrix[0].size();
  int maxSum = INT_MIN;
  int top = 0, bottom = 0, left = 0, right = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < n; k++) {
        for (int l = 0; l < m; l++) {
          int currSum = 0;
          for (int x = i; x <= k; x++) {
            for (int y = j; y <= l; y++) {
              currSum += matrix[x][y];
            }
          }
          if (currSum > maxSum) {
            maxSum = currSum;
            top = i;
            left = j;
            right = k;
            bottom = l;
          }
        }
      }
    }
  }
  cout << "The Top Left of the rectangle is: " << top << " " << left << endl;
  cout << "The Bottom Right of the rectangle is: " << bottom << " " << right << endl;
  cout << "The sum of this rectangle is: " << maxSum << endl;
}

Java Implementation

public static void maxMatrixSum(int[][] matrix) {
  int n = matrix.length;
  int m = matrix[0].length;
  int maxSum = -999999999;
  int top = 0, bottom = 0, left = 0, right = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < n; k++) {
        for (int l = 0; l < m; l++) {
          int currSum = 0;
          for (int x = i; x <= k; x++) {
 for (int y = j; y <= l; y++) {
              currSum += matrix[x][y];
            }
          }
          if (currSum > maxSum) {
            maxSum = currSum;
            top = i;
            left = j;
            right = k;
            bottom = l;
          }
        }
      }
    }
  }
  System.out.println("The Top Left of the rectangle is: " + top + " " + left);
  System.out.println("The Bottom Right of the rectangle is: " + bottom + " " + right);
  System.out.println("The sum of the rectangle is: " + maxSum);
}

Python Implementation

def maxMatrixSum(matrix):
    maxSum = -9999999
    n = len(matrix)
    m = len(matrix[0])
    top, left, right, bottom = None, None, None, None
    for i in range(n):
        for j in range(m):
            for k in range(n):
                for l in range(m):
                    currSum = 0
                    for x in range(i, k + 1):
                        for y in range(j, l + 1):
                            currSum += matrix[x][y]
                    if currSum > maxSum:
                        maxSum = currSum
                        top = i
                        left = j
                        right = k
                        bottom = l
    print("The Top Left of the Rectangle is: ", top, left)
    print("The Bottom Right of the Rectangle is: ", bottom, right)
    print("The maximum sum is: ", maxSum)

Complexity Analysis

• Time Complexity: O(n⁶)
• Space Complexity: O(1)

Optimal Approach

We will use Kadane’s Algorithm for finding the largest sum subarray (in 1D) to improve our time complexity over the naive approach. The key idea in this approach is that we will fix the left and right columns one by one and then for contiguous rows, we will find the maximum sum, for all possible choices of left and right column pairs with the help of Kadane’s Algorithm. The algorithm is as follows:

• Store the sum of elements in each row, from column, numbered left to right, in an array (stored[])
• By applying Kadane’s Algorithm in this stored[] array, we will obtain the maximum sum subarray of this array, which is equal to the maximum sum, that can be obtained with column boundaries from left to right.
• To obtain the overall maximum sum, we take the maximum of all such values of sums obtained so far till the algorithm terminates.

C++ Code

int kadaneAlgorithm(vector < int > & a, int & start, int & end, int n) {
  int currSum = 0, maxSum = INT_MIN;
  end = -1;
  int currStart = 0;
  for (int i = 0; i < n; i++) {
    currSum += a[i];
    if (currSum < 0) {
      currSum = 0;
      currStart = i + 1;
    } else if (maxSum < currSum) {
      maxSum = currSum;
      start = currStart;
      end = i;
    }
  }
  if (end != -1) {
    return maxSum;
  }
  int index = max_element(a.begin(), a.end()) - a.begin();
  start = end = index;
  maxSum = * max_element(a.begin(), a.end());
  return maxSum;
}
void maxMatrixSum(vector < vector < int >> & matrix) {
  int n = matrix.size();
  int m = matrix[0].size();
  int matrixLeft = -1, matrixRight = -1, matrixTop = -1, matrixBottom = -1;
  int maxSum = INT_MIN;
  vector < int > stored(n);
  int sum, start, end;
  for (int left = 0; left < m; left++) {
    stored.assign(n, 0);
    for (int right = left; right < m; right++) {
      for (int i = 0; i < n; i++) {
        stored[i] += matrix[i][right];
      }
      sum = kadaneAlgorithm(stored, start, end, n);
      if (maxSum < sum) {
        maxSum = sum;
        matrixLeft = left;
        matrixRight = right;
        matrixTop = start;
        matrixBottom = end;
      }
    }
  }
  cout << "The Top Left of the rectangle is: " << matrixTop << " " << matrixLeft << endl;
  cout << "The Bottom Right of the rectangle is: " << matrixBottom << " " << matrixRight << endl;
  cout << "The sum of this rectangle is: " << maxSum << endl;
}

Java Code

public static void maxMatrixSum(int[][] matrix) {
  int n = matrix.length;
  int m = matrix[0].length;
  int matrixLeft = -1, matrixRight = -1, matrixTop = -1, matrixBottom = -1;
  int maxSum = Integer.MIN_VALUE;
  int[] stored = new int[n];
  int sum, start = 0, end;
  for (int left = 0; left < m; left++) {
    Arrays.fill(stored, 0);
    for (int right = left; right < m; right++) {
      for (int i = 0; i < n; i++) {
        stored[i] += matrix[i][right];
      }
      int currSum = 0, greatestSum = Integer.MIN_VALUE;
      end = -1;
      int currStart = 0;
      for (int i = 0; i < n; i++) {
        currSum += stored[i];
        if (currSum < 0) {
          currSum = 0;
          currStart = i + 1;
        } else if (maxSum < currSum) {
          greatestSum = currSum;
          start = currStart;
          end = i;
        }
      }
      if (end != -1) {
        sum = greatestSum;
      } else {
        start = 0;
        end = 0;
        greatestSum = stored[0];
        for (int i = 0; i < n; i++) {
          if (greatestSum < stored[i]) {
            greatestSum = stored[i];
            start = i;
            end = i;
          }
        }
        sum = greatestSum;
      }
      if (maxSum < sum) {
        maxSum = sum;
        matrixLeft = left;
        matrixRight = right;
        matrixTop = start;
        matrixBottom = end;
      }
  }
  }
  System.out.println("The Top Left of the rectangle is: " + matrixTop + " " + matrixLeft);
  System.out.println("The Bottom Right of the rectangle is: " + matrixBottom + " " + matrixRight);
  System.out.println("The sum of the rectangle is: " + maxSum);
}

Python Code

def kadaneAlgorithm(a, start, end, n):
    currSum = 0
    maxSum = -9999999
    end[0] = -1
    currStart = 0
    for i in range(n):
        currSum += a[i]
        if currSum < 0:
            currSum = 0
            currStart = i + 1
        elif maxSum < currSum:
            maxSum = currSum
            start[0] = currStart
            end[0] = i
    if end[0] != -1:
        return maxSum
    maxSum = max(a)
    for i in range(n):
        if maxSum == a[i]:
            start = i
            end = i
    return maxSum


def maxMatrixSum(matrix):
    maxSum = -9999999
    matrixLeft, matrixRight, matrixTop, matrixBottom = None, None, None, None
    n = len(matrix)
    m = len(matrix[0])
 stored = [0] * n
    sum = 0
    start = [0]
    end = [0]
    for left in range(m):
        stored = [0] * n
        for right in range(left, m):
            for i in range(n):
                stored[i] += matrix[i][right]
            sum = kadaneAlgorithm(stored, start, end, n)
            if sum > maxSum:
                maxSum = sum
                matrixLeft = left
                matrixRight = right
                matrixTop = start[0]
                matrixBottom = end[0]
    print("The Top Left of the Rectangle is: ", matrixTop, matrixLeft)
    print("The Bottom Right of the Rectangle is: ", matrixBottom, matrixRight)
    print("The maximum sum is: ", maxSum)

Complexity Analysis

• Time Complexity: O(n³)
• Space Complexity: O(n)

Practice Problem

Maximum Sum Square Submatrix

FAQs

Q. What is Kadane’s Algorithm used for?
A. Kadane’s Algorithm is used to find the largest sum subarray in a 1D array or list.

Q. Will this algorithm work if all the array elements are negative?
A. Yes, even in that case the algorithm will work, and the result should be equal to the largest number in the array.