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.
Nicely explained...
ReplyDeletewhen I read the problem for the first time,
I did not know this algorithm..
I also assumed that given NxN matrix,
i have to find out the submtrix of size KxK where k<N
I tried solving it myself and I came uptil Step 2,and (honestly)later had difficulty in coming till 3 and then I search it and landed to your blog...
However the way i reached till step 2 was different...i was trying to solve it in N^2 LOL
;o)
As in step 1 you created column sum matrix...
along with that I also created row sum matrix...
and later on an intersection matrix of both ..and answer was in front of my eyes(find the maximum sum in one dimension) and i could not see it...
How do I do this part?
ReplyDelete[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]
I'm having trouble getting past this part, any help would be good.
Thanks for clear explanation..:)
ReplyDeleteExcellent tutorial. Was scanning the net for something similar the entire day. Here's the code I wrote in python for it:
ReplyDeleteimport time
def kadane(aSeq):
transientTotal=aSeq[0]
transientStartIndex=0
total=aSeq[0]
start=0
end=0
for i in range(1,len(aSeq)):
transientTotal+=aSeq[i]
if transientTotal<aSeq[i]:
transientTotal=aSeq[i]
transientStartIndex=i
if total<transientTotal:
total=transientTotal
start=transientStartIndex
end=i
return (total,start,end)
def maxSubMatrix(aSeq):
rows=len(aSeq)
cols=len(aSeq[0])
prefix=[[i-i for i in range(0,cols)],
[i-i for i in range(0,cols)],
[i-i for i in range(0,cols)]]
for i in range(0,rows):
for j in range(0,cols):
prefix[i][j]=aSeq[i][j]
top=left=bottom=right=-1
for i in range(0,cols):
for j in range(1,rows):
prefix[j][i]+=prefix[j-1][i]
summer=-999999
for i in range(0,rows):
for j in range(i,rows):
if i==0:
temp=prefix[j]
else:
temp=[prefix[j][t]-prefix[i-1][t] for t in range(0,cols)]
kadaneTuple=kadane(temp)
if(summer<kadaneTuple[0]):
summer=kadaneTuple[0]
top=i
left=kadaneTuple[1]
bottom=j
right=kadaneTuple[2]
output=[]
for i in range(top,bottom+1):
x=[aSeq[i][j] for j in range(left,right+1)]
output.append(x);
print summer,output
if __name__=="__main__":
seq=[[-3,2,3],
[-9,5,6],
[-1,-2,-3]]
start=time.time()
maxSubMatrix(seq)
print "%d (ms)" % ((time.time()-start)*1000)
good explanation ....really helped me a lot....
ReplyDelete