> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/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://media.geeksforgeeks.org/wp-content/cdn-uploads/rectangle-11.png)

```java
class Solution {
    public int kadane(int[] arr) {
        int curr_sum = 0;
        int max = Integer.MIN_VALUE;
        for (int x : arr) {
            curr_sum += x;
            max = Math.max(max, curr_sum);
            if (curr_sum < 0)
                curr_sum = 0;
        }
        return max;
    }

    public int maxSumSubmatrix(int[][] matrix) {
        if (matrix.length == 0)
            return 0;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < matrix[0].length; i++) {
            int[] sum = new int[matrix.length];
            for (int j = i; j < matrix[0].length; j++) {
                for (int k = 0; k < matrix.length; k++)
                    sum[k] += matrix[k][j];
                int bestSum = kadane(sum);
                ans=Math.max(ans,bestSum);
            }
        }
        return ans;
    }
}
```