Kadane’s Algorithm: Maximum Sum Rectangle In A 2D Matrix

Problem Statement:

You are given a 2D matrix, you need to find the maximum sum among all the possible submatrix.

Solution Explanation:

We can solve the problem with the help of kadane algorithm.

But we know that the kadane algorithm will only work on the 1D array. So we need to convert 2D algorithm into 1D algorithm.

For that, we will consider a left and right boundary and a temp array.

For each pair, we will add the elements, where in each element represents the sum of rows between the current left and right columns.

Time Complexity: O(1)
Space Complexity: O(1)

Above Example explanationL

Pass 1:

left = 0, temp = [0, 0, 0]

Pass 2:

add left 0 right 0
temp =[1, -3, 1]
Apply Kadanes algorithm -> Max Subarray Sum = 1

Pass 2:

add left 0 right = 1
temp =[1+2, -3+4, 1-1] = [3, 1, 0]
Apply Kadanes algorithm -> Max Subarray Sum = 4

Pass 3:

add left 0 right = 2
temp =[1+2-1, -3+4+2, 1-1+3] = [2, 3, 3]
Apply Kadanes algorithm -> Max Subarray Sum = 8

Now repeat the same steps with left = 1.

Code Solution

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <climits>
using namespace std;



int kadaneAlgorithm(int arr[], int n)
{
	int currentSum = 0;
	
	int maxSum = INT_MIN;
    
	for(int currIndex = 0; currIndex < n; currIndex++)
	{
		currentSum += arr[currIndex];

		maxSum = max(maxSum, currentSum);
		currentSum = (currentSum < 0) ? 0 : currentSum;
	}

	return maxSum;
}

int solution(vector<vector<int>>& matrix)
{
   	int row = matrix.size();
    int column = matrix[0].size();
	int maxSum = INT_MIN;
	int temp[row];
    
	for(int left = 0; left < column; left++)
	{
		//reset temp
		for(int i = 0; i < row; i++)
		{
			temp[i] = 0;
		}

		for(int right = left; right < column; right++)
		{
			for(int i = 0; i < row; i++)
			{
				temp[i] += matrix[i][right];
			}
            
			int sum = kadaneAlgorithm(temp, row);
            
			maxSum = max(maxSum, sum);
		}
	}

	return maxSum;
}


int main() {
    vector<vector<int>> mat = {{1, 2, -1},
                               {-3, 4, 2}, 
                               {1, -1, 3}};

    cout << solution(mat) << endl;             

    return 0;
}

Output

9