Kadane's 2D Algorithm

Kadane's 2D algorithm uses Kadane's 1D algo. So i expect anyone to know Kadane's 1D algo.

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.

- 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

- 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

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