Last Updated: 10 Jan, 2021
Maximum Sum Rectangle
Easy
Asked in companies
You are given a matrix ‘ARR’ with ‘N’ rows and ‘M’ columns. Your task is to find the maximum sum rectangle in the matrix.
Maximum sum rectangle is a rectangle with the maximum value for the sum of integers present within its boundary, considering all the rectangles that can be formed from the elements of that matrix.
For Example
Consider following matrix:
The rectangle (1,1) to (3,3) is the rectangle with the maximum sum, i.e. 29.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the number of rows and number of columns respectively.
The next ‘N’ lines contain ‘M’ space-separated integers denoting the elements of ARR.
Output Format
For each test case, print the value of the sum for the maximum sum rectangle.
Print the output of each test case in a separated line.
Note
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 10
1 <= M, N <= 75
-10^5 <= ARR[i][j] <= 10^5
Time Limit: 1 sec
Approaches
We will iterate through all the rectangles of the matrix with the help of nested loops and return the maximum sum found.
Algorithm
- We will iterate over the ‘leftBoundary’, ‘rightBoundary’, ‘upBoundary’, ‘ ‘downBounday’ of the rectangle with the help of four nested loops.
- For each of the boundaries, we will find the sum of the rectangle contained in it.
- We finally return the maximum obtained sum.
In this approach, we will use the prefix sum, so that we don’t have to iterate on the elements of sub-matrix for finding the sum of a sub-matrix.
Let pref[][] store the prefix sum of the given matrix.
pref[i][j] is the sum of the sub-matrix whose top-left corner is at (0, 0) and bottom right corner is at (i, j).
For finding the prefix matrix, first, we will do the row-wise sum and then we will do the column-wise sum.
For example:
Sum of a sub-matrix (R1, C1, R2, C2) {where (R1, C1) denotes the top-left corner of the sub-matrix and (R2, C2) denotes the bottom-right corner of the sub-matrix} is:
SUM = pref[R2][C2] - pref[R2][C1-1] - pref[R1-1][C2] + pref[R1-1][C1-1].
We can optimize the brute force with the help of the ‘Kadane algorithm’ for a 1-D array which is used to find the maximum subarray sum. We will fix the left and right boundaries for a rectangle. We will then store the sum of elements of the matrix from ‘leftBoundary’ to ‘rightBoundary’, in an auxiliary array ‘temp’ of size ‘N’. We will then use the ‘Kadane algorithm’ to find the maximum subarray sum for ‘temp’.
Algorithm
- Initialize variable ‘maxSum’ to a minimum value.
- We define a ‘temp’ array, whose size is the same as N.
- For LEFT from 0 to the M, do:
- Fill the ‘temp’ array with 0.
- For RIGHT from LEFT to M - 1, do:
- For each row i, do temp[i] =temp[i] + temp[i][RIGHT] for each 0 <= i < ROW
- Assign sum = kadaneAlgorithm(temp, N)
- if sum > maxSum, then assign maxSum = sum
- Return ‘maxSum’.
The function kadaneAlgorithm has two parameters ARR and N and calculates the SUM as follows:
- Initialize variable ‘sum’ to 0 and ‘maxSum’ to a minimum value.
- We will iterate through the ARR. We will maintain the variable ‘sum’ denoting the maximum sum of prefix elements. Let the current index be ‘currIndex’.
- For each iteration, we will-
- Add ARR[currIndex] to sum.
- Update maxSum if the value of sum becomes greater than maxSum.
- If sum becomes negative, we will replace the value of the sum with 0.
- The value stored in maxSum will be our answer.