Maximum sum rectangle in a 2D matrix

December 7, 2021

Maximum sum rectangle in a 2D matrix

In the Maximum sum rectangle in a 2D matrix problem, we have to find the largest sum rectangle in a matrix. This problem is an application of kadane’s algorithm. In this article, we will provide C++ Solution with an explanation.

Maximum sum rectangle in a 2D matrix Problem Description

Given a matrix of integers. The dimensions of matrix are r*c (row*columns). Return the maximum sum possible of a rectangle in the matrix.

Input

First line contains two integers r & c.
Next r lines contains c integers each.

Output

Single Integer denoting the maximum sum.

Maximum sum rectangle in a 2D matrix Solution

Basic Solution

The basic approach is to iterate over all rectangles. Since we are dealing with a 2-D matrix we require 4 loops to iterate and 2 loops to find sum. Thus the time complexity of this approach is O((r^3)*(c^3)).

Optimized Solution

Prerequisites – Kadane’s Algorithm

For defining a rectangle we need it’s top, bottom, left & right edges. So we can iterate over all rows using two nested loops ie we can generate all possible sets of top and bottom edges. While iterating we will maintain a prefix sum array and apply kadane’s algorithm to find best left and right edges for a given top & bottom edges.

Time Complexity – O((r^r)*c)

Space Complexity – O(c)

Code

#include <bits/stdc++.h>
using namespace std;
int r, c;
int mat[105][104];
int kadaneAlgo(int arr[], int n)
{
    int cSum = 0, mxSum = INT_MIN;

    // Finding the maximum element
    for (int i = 0; i < n; i++)
        mxSum = max(arr[i], mxSum);
    //Since the maximum element is negative
    if (mxSum <= 0)
        return mxSum;

    // Kadane’s Algorithm
    for (int i = 0; i < n; i++)
    {
        cSum += arr[i];
        if (cSum < 0)
            cSum = 0;
        mxSum = max(mxSum, cSum);
    }
    return mxSum;
}
int mxSumRect()
{
    int mxSum = INT_MIN;

    //fix top & bottom
    for (int top = 0; top < r; top++)
    {
        int arr[c] = {0};
        for (int bottom = top; bottom < r; bottom++)
        {
            for (int j = 0; j < c; j++)
                arr[j] += mat[bottom][j];
            int sum = kadaneAlgo(arr, c);
            mxSum = max(mxSum, sum);
        }
    }
    return mxSum;
}
int main()
{
    cin >> r >> c;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            cin >> mat[i][j];

    cout << mxSumRect() << endl;
    return 0;
}

Output

4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6
29