Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
Add Comment
Please, Sign In to add comment