Running One Iteration:
0
|
-2
|
-7
|
0
|
9
|
2
|
-6
|
2
|
-4
|
1
|
-4
|
1
|
-1
|
8
|
0
|
-2
|
At i=0: (to n-1)
Reset Total Array
0
|
0
|
0
|
0
|
At k=i=0: (to n-1)
Reset sum and current_max
At j=0: (to n-1)
total[j=0] += a[k=0][j=0] = 0
Sum += total[j=0] = 0
If (sum < 0) sum=0
If (sum > current_max) sum = current_max
Doing this for j=1 to 3
j=1 -> Sum = -2
j=2 -> Sum = -7
j=3 -> Sum = 0
0
|
-2
|
-7
|
0
|
At this point it’s like we ran kadane’s algorithm for row1
At k=1:
Reset sum and current_max
At j=0
total[j=0] += a[k=1][j=0] = 0+9 = 9
Sum += total[j=0] = 9
If (sum < 0) sum=0
If (sum > current_max) sum=current_max = 9
Doing this for j=1 to 3
j=1 -> Sum = -2+2 = 0
j=2 -> Sum = -7-6 = -13
j=3 -> Sum = 0+2 = 2
0+9=9
|
0
|
-13
|
2
|
At this point it’s like we ran kadane’s algorithm for sum array (row1+row2).
No comments:
Post a Comment