Well Explained

Kadane's 1D algo, finds the maximum contigous sum in an 1D array in O(n) time complexity.

Now to the 2D algo. Lets consider the problem of finding a maximum sub-matrix from a matrix. Consider the below matrix 'm'-

1 2 -1
-3 -1 -4
1 -5 2

the maximum sub matrix in this example is - [1 2]

To do this programatically, do follow the steps below.

1. Step1

Create a temp matrix temp[3][3]. Any element in this matrix temp[i][j] is the sum of all temp[1][j], temp[2][j]…temp[i][j].

That's temp[i][j] = temp[1][j]+temp[2][j].+..+temp[i][j].

So our temp matrix is

1 2 -1
-2 1 -5
-1 -4 -3
This has a time complexity of n^2

1. Step2

Now in this 3 x 3 matrix, the row can be grouped as [1],[1,2],[1,2,3],[2],[2,3],[3].

We can find the sum of these above row combinations using the temp matrix we created as below.

[1] = Row 1 in temp matrix - [1,2,-1]
[1,2] =Row 2 in temp matrix - [-2,1,-5]
[1,2,3] = Row 3 in temp matrix - [-1,-4,-3]
[2] = Row 2 - Row 1 in temp matrix - [-3,-1,-4]
[2,3] = Row 3 - Row 1 in temp matrix - [-2,-6,-2]
[3] = Row 3 - Row 2 in temp matrix - [1,-5,2]

This has a time complexity of n^2

1. Step3

Now i provide each of the above row to Kadane's 1D algo to find the maximum contigous sub-sequence. After the algo processed all the rows the maximum we have is for row [1] - column 0 to column 1.

So the maximum sub matrix is from m[0][0] to m[0][1] thats [1 2].

The time complexity is n^3.
This solution will work for any matrix including positive and negative numbers.