Finding maximum sum subrectangle

Algorithm Type Algorithm Gist Time Complexity
Simplistic brute-force 1.ย ย ย  Set the positions of the Top-Left and Bottom-Right corners of a subrectangle.
2.ย ย ย  Iterate through all the rows and columns sequentially and find the maximum sum sub-rectangle.
O ( n 6 )
Dynamic programming : Aggregate rectangles 1.ย ย ย  Convert the rectangle into an aggregate rectangle using inclusion-exclusion principle.
2.ย ย ย  Find the maximum sum subrectangle using dynamic programming and inclusion-exclusion principle.
O ( n 4 )
Dynamic programming : Kadane’s algorithm with row summations 1.ย ย ย  Build all sub-rectangles between the left-most and right-most column.
2.ย ย ย  For every single subrectangle get row summations.
3.ย ย ย  Apply Kadane’s algorithm on the sub-rectangle for finding the maximum sum sub-rectangle.
O ( n 3 )

Copyright (c) 2019-2021,
All rights reserved.