# 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.

[![](https://www.geeksforgeeks.org/wp-content/uploads/rectangle-11.png)](https://www.geeksforgeeks.org/wp-content/uploads/rectangle.png)

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)

```java
```

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