| 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 ) |