> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/dynamic_programming/maximum-sum-rectangle-in-a-2d-matrix.md).

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