In this article we will be discussing an efficient approach to solve the problem of finding maximum subarray sum in a 2D Matrix.

Link to the problem: GFG

Given the above matrix, blue rectangle denotes the maximum sum rectangle.

The above problem becomes interesting as the size of the rectangle is not predefined.

It could be 1x1, 1x2, 3x3, etc. Hence, most of the people get TLE (Time Limit Exceeded) error, as they try to work out the sum for every possible configuration of the rectangle in the matrix.

This naive solution results in O(n^6) time complexity as it makes use of 6 nested for loops:

1. 4 for the top left and bottom right coordinates of the rectangle.
2. 2 for taking the sum of the elements enclosed by the rectangle.

However, we could reduce the 2D matrix to a 1D array and apply Kadane's Algorithm to bring down the time complexity to O(n^3).

Kadane's Algorithm: Background

Kadane's Algorithm is the most optimal solution for finding out the maximum subarray sum for 1D arrays via a single iteration through the array.

If you want to understand max sum subarray and the various methods to implement it, including the Kadane's Algorithm, have a read at one of my article.

After going through the above article, one could easily notice that kadane's algorithm tries out every possible window size in a single iteration through the array.

Let us take a small example to better comprehend this concept.

array = [-2,1,-3,4,-1,2,1,-5,4]
When we apply Kadane's algo, it takes into account the following possible optimal sum subarrays:
1. [-2]
2. [1]
3. [1, -3]
4. [4]
5. [4, -1]
6. [4, -1, 2]
7. [4, -1, 2, 1]
8. [4, -1, 2, 1, -5]
9, [4, -1, 2, 1, -5, 4]

The max sum is found via configuration-7 resulting in the answer 6.

Important takeaway: If you pass a matrix row to this algorithm, it tries out all possible column combinations and returns the output of the most optimal row, column configuration.

This means in the given array (row of a matrix), the max sum is obtained by taking columns indexed [3, 4, 5, 6] ie. we got the output corresponding to a 1x4 rectangle.

If I pass the cumulative sum of 2 rows reduced to 1D array to Kadane's algorithm and max sum is obtained via columns indexed [2, 3, 4, 5], this would imply the output corresponding to a 2x4 rectangle.

In simple words, we don't need to worry about column configurations and could just pass different row configurations to this algorithm one by one.

Detailed Step by Step working of the Algorithm 🔥

Let us take a 3x3 matrix

mat = {
    {1, 2, 3},
    {-4, 3, 6}, 
    {9, 8, -10}
}

Now there could be lot of rectangles of size 1x1, 1x2, 1x3, 2x1, 2x2, 2x3, 3x1, 3x2 and 3x3. Well thanks to Kadane's algorithm, we don't need to go check each of these rectangles in the matrix.

Step-1: Consider the first row in the temp array.

arr = {1, 2, 3}

Apply Kadane's Algorithm, we get max_sum = 6 which corresponds to rectangle of dimension 1x3.

Rectangle selected: {1, 2, 3}

Now, add the second row elements in this temp array.
updated arr = {-3, 5, 9}

Apply Kadane's Algorithm, we get max_sum = 14 which corresponds to rectangle of dimension 2x2.

Rectangle selected: {{2, 3}, {3, 6}}

Now, add the third row elements in this temp array.
updated arr = {6, 13, -1}

Apply Kadane's Algorithm, we get max_sum = 19 which corresponds to rectangle of dimension 3x2.

Rectangle selected: {{1, 2}, {-4, 3}, {9, 8}}

Step-2: Consider the second row in the temp array.

arr = {-4, 3, 6}

Apply Kadane's Algorithm, we get max_sum = 9 which corresponds to rectangle of dimension 1x2.

Rectangle selected: {3, 6}

Now, add the third row elements in this temp array.
updated arr = {5, 11, -4}

Apply Kadane's Algorithm, we get max_sum = 16 which corresponds to rectangle of dimension 2x2.

Rectangle selected: {{-4, 3}, {9, 8}}

Step-3: Consider the third row in the temp array.

arr = {9, 8, -10}

Apply Kadane's Algorithm, we get max_sum = 17 which corresponds to rectangle of dimension 1x2.

Rectangle selected: {9, 8}

The final answer would be maximum of all these max_sum values ie. 19 which corresponds to rectangle of dimension 3x2 : {{1, 2}, {-4, 3}, {9, 8}}.

Let us now go through the C++ implementation of the same.

#include <bits/stdc++.h>
using namespace std;

class Solution {
  public:
    // return max sum in the given vector
    int kadane_helper(int *arr, int n) {
        int max_sum = INT_MIN, cur_sum = 0;
        for(int i = 0; i < n; i++) {
            cur_sum += arr[i];
            max_sum = max(max_sum, cur_sum);
            if(cur_sum < 0)
                cur_sum = 0;
        }
        return max_sum;
    }

    int maximumSumRectangle(int R, int C, vector<vector<int>> &mat) {
        // code here
        int max_sum = INT_MIN;
        // traverse the rows
        for(int i = 0; i < R; i++) {
            // create temp array to store row by row sums
            int arr[C] = {0};
            // take sum of rows below this, expansion of the rows of the rectangle
            for(int j = i; j < R; j++) {
                // traverse the entire column and take sum of values
                for(int col = 0; col < C; col++)
                    arr[col] += mat[j][col];
                // one row is included
                // find the max sum of this temp vector using kadane's algo
                max_sum = max(max_sum, kadane_helper(arr, C));
            }
        }
        return max_sum;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        int N, M;
        cin >> N >> M;
        vector<vector<int>> v(N, vector<int>(M));
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) cin >> v[i][j];
        Solution ob;
        cout << ob.maximumSumRectangle(N, M, v) << "\n";
    }
}

We have used the kadane's algorithm as our helper function which takes in an array of size n.

The problem is solved via 3 nested for loops where the outermost for loop is used to traverse the rows. For every row, we need to consider the current row elements and the rows below it. This helps us in fixing the row dimension of the output rectangle matrix sum. Store the elements of the current row in a temporary array and pass this array to the Kadane's Algorithm. Now add the elements of the next rows to this temporary array and repeat the same process.

That's all for this article. Hope you were able to learn something new.

If you want to test your understanding, try solving a similar question on LeetCode. LeetCode-363

Hint: You need to make some modifications in the Kadane's Algorithm helper function as the max sum should not exceed k.

Hope you enjoyed this article, feel free to connect with me on LinkedIn and github.