Finding maximum sum subrectangle using aggregate rectangles
Finding the maximum sum subrectangle in a two dimensional array/matrix.
A brute-force way of finding the maximum sum sub-rectangle is to set the postion of the top-left and bottom-right corners of the sub-rectangle and adding the integers within it while iterating through all the rows sequentially. Setting all the top-left and bottom-right corners of the sub-rectangles within a given rectangle takes O ( n^4 ) time, adding the elements within it takes O ( n^2 ) time. Thus the simplistic brute-force algorithm takes O ( n^6 ) time.
A better ( not the best ) approach than the above is shown below that has the time complexity of O ( n^4 ).
Dynamic programming approach of finding the maximum sum sub-rectangle
- Convert the given rectangle into an aggregate rectangle. In an aggregate rectangle, each integer at position r (row) and c (column) indicates the sum of a sub-rectangle whose top-left corner is ( 0, 0 ) and bottom-right corner is ( r, c ). The aggregate rectangle can be calculated in O ( n ^ 2 ) time and is based on the inclusion-exclusion principal. Inclusion-Exclusion principle 1. For each row r in ROWS : 2. For each column c in COLS : 3. If r > 0 ( Add integers from the row above ) : rectangle [ r ] [ c ] += rectangle [ r - 1 ] [ c ] 4. If c > 0 ( Add integers from the column to the left ) : rectangle [ r ] [ c ] += rectangle [ r ] [ c - 1 ] 5. If r > 0 and c > 0 ( Subtract the integer at the diagonal position that got added twice during the previous row and column additions ) : rectangle [ r ] [ c ] -= rectangle [ r - 1 ] [ c - 1 ]
Once an aggregate rectangle as shown below is obtained, finding the maximum sum subrectangle can be done in O ( n^4 ).
All possible subrectangles can be obtained by setting the position of the top-left and bottom-right corner(s). The sum of the subrectangle thus formed can be deduced by using the inclusion-exclusion principle.
Example of finding the sum of a subrectangle with co-ordinates : Top-Left ( 2, 2 ) and Bottom-Right ( 3, 3 ) Left is 2 and 2 > 0 : sum of subrectangle = 2 - (-20) = 22 ( subtract the aggregate rectangle on the left ) Top is 2 and 2 > 0 : sum of subrectangle = 22 - 8 = 14 ( subtract the aggregate rectangle above ) Left and Top both are greater than 0 : sum of rectangle = 14 + 11 = 25 ( add the aggregate rectangle in the diagonal location above as it got subtracted twice )
Time complexity of finding the maximum sum subrectangle : O ( n^4 ). If the length is ‘l’ and the breadth is ‘b’ then the time complexity is O ( l^2 . b^2 ) which is effectively O( n^4 ) if l equals b equals n.
The time complexity of finding the maximum sum subrectangle can be further reduced to O ( n^3 ) using dynamic programming with Kadane’s algorithm.
C++
Python : Maximum Sum SubRectangle implementation using Dynamic Programming in Python3
#!/usr/bin/python3
def GetMaxSumRectangle(matrix):
rows = len(matrix)
cols = len(matrix[0])
# Inclusion Exclusion Principle
for r in range(rows):
for c in range(cols):
# Add element from the previous column
if(r > 0):
matrix[r][c] += matrix[r-1][c]
# Add element from the previous row
if(c > 0):
matrix[r][c] += matrix[r][c-1]
# Subtract diagonal element that got added twice from previous row and column additions
if(r > 0 and c > 0):
matrix[r][c] -= matrix[r-1][c-1]
maxsum = -100*100*100
for i in range(rows):
for j in range(cols):
for k in range(i, rows):
for l in range(j, cols):
sum_subrectangle = matrix[k][l]
if(i > 0):
sum_subrectangle -= matrix[i-1][l]
if(j > 0):
sum_subrectangle -= matrix[k][j-1]
if(i > 0 and j > 0):
sum_subrectangle += matrix[i-1][j-1]
if(sum_subrectangle > maxsum):
# Co-ordinates of maximum sum sub rectangle
from_row = i
from_column = j
to_row = k
to_column = l
maxsum = sum_subrectangle
print("Maximum sum in sub-rectangle: "+str(maxsum))
print("Maximum sum rectangle co-ordinates: (" + str(from_row) + "," + str(from_column) + ")" + "-" + "(" + str(to_row) + "," + str(to_column) + ")")
matrix1 = [[ 1, -2, -6, 0 ],
[ 9, 3, -5, 3 ],
[ -5, 1, -4, 1 ],
[ -3, 7, 0,-3 ],
]
GetMaxSumRectangle(matrix1)
matrix2 = [[ 8, -2, -6, 11 ],
[ 9, -4, -5, -3 ],
[-5, -16, 14,-1 ],
[-3, -7, -1, 13 ],
]
GetMaxSumRectangle(matrix2)
Output
Maximum sum in sub-rectangle: 12
Maximum sum rectangle co-ordinates: (1,0)-(1,1)
Maximum sum in sub-rectangle: 25
Maximum sum rectangle co-ordinates: (2,2)-(3,3)