Last active
February 9, 2018 12:12
-
-
Save nberserk/a54e9e3892669f311330b6a8fde9d665 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int kadane2d(int[][] m){ | |
| int row = m.length; | |
| if(row==0)return 0; | |
| int col = m[0].length; | |
| int ret = Integer.MIN_VALUE; | |
| for (int left = 0; left < col; left++) { | |
| int[] sum = new int[row]; // reuse this | |
| for (int right = left; right < col; right++) { | |
| for (int i = 0; i < row; i++) { | |
| sum[i] += m[i][right]; | |
| } | |
| int curMax=sum[0]; | |
| int max=sum[0]; | |
| for (int i = 1; i < row; i++) { | |
| curMax = Math.max(curMax+sum[i], sum[i]); | |
| max = Math.max(curMax, max); | |
| } | |
| ret=Math.max(ret, max); | |
| } | |
| } | |
| return ret; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment