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-2020,
All rights reserved.