| 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 ) |
© 2019-2026 Algotree.org | All rights reserved.
This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org
"The best error message is the one that never shows up. - Thomas Fuchs"