Kadane2D.java

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;
    }