### Question

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.

### Analysis

**Note that this is a difficult(and high-frequency) question**.

Try convert this question to “**max sum in 1D array**” by sum up all numbers in the same column. (we know that in 1D array, the algo runs O(n) time)

There’s in total O(n^{2}) combinations of ways to sum up a column. So the **total time complexity is O(n ^{3})**.

### Solution

Traverse matrix at row level.

have a temporary 1-D array and initialize all members as 0.

For each row do following

- add value in temporary array for all rows below current row
- apply 1-D kadane on temporary array
- if your current result is greater than current maximum sum, update.

### Code

**written by me**

```
public int maxSum(int[][] A) {
int m = A.length;
int n = A[0].length;
int maxResult = Integer.MIN_VALUE;
for (int i = 0; i < m; i++) {
int[] temp = new int[n];
for (int j = i; j < m; j++) {
// from row#i to row#(m-1), add the number into temp[]
for (int k = 0; k < n; k++) {
temp[k] += A[j][k];
}
// find max sum for 1D array
maxResult = Math.max(maxResult, maxSum(temp));
}
}
return maxResult;
}
private int maxSum(int[] B) {
int sumSoFar = 0;
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < B.length; i++) {
maxSum = Math.max(maxSum, sumSoFar + B[i]);
sumSoFar = Math.max(0, sumSoFar + B[i]);
}
return maxSum;
}
```