# 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/](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.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/)

[https://www.youtube.com/watch?v=-FgseNO-6Gk](https://www.youtube.com/watch?v=-FgseNO-6Gk)

[https://prismoskills.appspot.com/lessons/Dynamic\_Programming/Chapter\_07\_-\_Submatrix\_with\_largest\_sum.jsp](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](https://www.tutorialspoint.com/Maximum-sum-rectangle-in-a-2D-matrix)
