Maximum Sum Rectangle in a 2D Matrix

Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29.

Source: https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/

Analysis & Solution

Basically, kadane's algorithm (complexity: O(n)) is used inside a naive maximum sum sub-array problem (complexity: O(n2)). This gives a total complexity of O(n3)

Reference

https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/

https://www.youtube.com/watch?v=-FgseNO-6Gk

https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_07_-_Submatrix_with_largest_sum.jsp

https://www.tutorialspoint.com/Maximum-sum-rectangle-in-a-2D-matrix