Last Updated: 17 Nov, 2020

Maximum sum rectangle

Hard

Asked in companies

Solve now

Problem statement

You are given an M X N matrix of integers ARR. Your task is to find the maximum sum rectangle.

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.

A rectangle is a 2-D polygon with opposite sides parallel and equal to each other.

For example:

Consider following matrix:

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

The rectangle (1,1) to (3,3) is the rectangle with the maximum sum, i.e. 29.

 1   2 -1 -4  -20
-8 |-3  4  2 |  1
 3 | 8  10 1 |  3
-4 |-1  1  7 | -6

Input Format :

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.
The first line of each test case contains two space-separated integers M and N representing the size of the matrix ARR.
Each of the next M lines contains N space-separated integers representing the elements of the matrix ARR.

Output Format :

For each test case, return the value of the sum for the maximum sum rectangle.

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 <= 100
-10^5 <= ARR[i] <=10^5

Time Limit : 1 sec

Solve now

Approaches

01 Approach

In this approach, we'll try to consider each rectangle that can be formed using elements of the array. To do this we fix (X1,Y1) coordinates of starting vertex and iterate through the matrix for every pair (X2,Y2) as the coordinates of ending vertex. Now we have a rectangle with coordinates (X1,Y1), (X1,Y2), (X2,Y1) and (X2,Y2).

We'll find the sum of elements within this rectangle and compare it with MAXSUM. if it is greater than MAXSUM, we'll update the value of MAXSUM.

Consider ARR[i][j] for each 0<=i<M and 0<=j<N, Initialize STARTX to i and STARTY to j do:
1. Consider ARR[m][n] for each 0<=m<M and 0<=n<N, Initialize ENDX to m and ENDY to n do:
  1. Calculate SUM from ARR[STARTX][STARTY] to ARR [ENDX][ENDY]
  2. If SUM>MAXSUM assign MAXSUM = SUM.

Solve now

02 Approach

Initialize variable MAXSUM to Integer.MIN_VALUE.
Define a TEMP array, whose size is same as rows of 2D matrix ARR
For LEFT from 0 to the number of columns in the ARR, do:
- Fill temp array with 0s
- For RIGHT from LEFT to the column of matrix -1, do:
  - For each row i, do TEMP[i] =TEMP[i]+ ARR[i][RIGHT] for each 0<=i<ROW
  - Assign SUM = kadaneAlgorithm(temp, start, end, number of rows)
  - if SUM > MAXSUM, then assign MAXSUM = SUM
Return MAXSUM

The function kadaneAlgorithm has four parameters ARR, START, END and N and calculate the SUM as follows:

Initialize variable SUM to 0 and MAXSUM to Integer.MIN_VALUE
Initialize END to -1 and TEMPSTART to 0
For ARR[i] for each 0<=i<N, do:
- Add ARR[i] to SUM.
- If SUM < 0, then assign SUM equal to 0 and TEMPSTART to i + 1
- Else, if sum > maxSum, then assign MAXSUM = SUM, START = TEMPSTART and END = i
if END ≠ -1, then return MAXSUM
Assign MAXSUM, the value of array[0] and START = 0 and END = 0
For each ARR[i] 0<=i<N do:
- If ARR[i] > MAXSUM, then assign MAXSUM = ARR[i], START = i and END = i
return MAXSUM

Solve now