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