Maximum Sum Rectangle

Easy
0/40
Average time to solve is 15m
profile
Contributed by
235 upvotes
Asked in companies
GojekAdobePhonePe

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1
2
1 2
-1 1
2 2
-1 1
2 2
Sample Output 1
1
4
Explanation of Input 1
The maximum sum rectangle corresponding to the first test case is-


The maximum sum rectangle corresponding to the second test case is-

Sample Input 2
1
4 5
1 2 -1 -4 -20
-8 -3  4 2 1
3  8 10 1 3
-4 -1 1 7 -6
Sample Output 2
29
Hint

Can we iterate over all possible rectangles?

Approaches (3)
Brute Force

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.
Time Complexity

O((N * M) ^ 3), where N denotes the number of rows of the matrix and M denotes the number of columns of the matrix.

 

We will iterate over all the boundaries of the rectangle in O((N * M) ^ 2) time. For each rectangle, we are finding out its sum in O(N * M) time.

Hence, overall time complexity will be O((N * M) ^ 2 * (N * M)) = O((N * M) ^ 3).

Space Complexity

O(1)

 

Constant space is used.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Maximum Sum Rectangle
Full screen
Console