Problem statement: Find the maximal sum of elements in a rectangular region of an integer matrix 

Solution:  

    public static int getMax(int[][] A) {

        assert (A != null && A.length > 0 && A[0].length > 0);

        int result = 0; // maximum profit of a rectangle

        int M = A.length;

        int N = A[0].length;

        if (M > N) {

            // transpose

            int[][] A1 = new int[N][M];

            for (int j = 0; j < N; j++) {

                for (int i = 0; i < M; i++) {

                    A1[j][i] = A[i][j];

                }

            }

            A = A1;

            M = A1.length;

            N = A1[0].length;

        }

        int[][] sum = new int[M+1][N+1];

        for (int i = 1; i < M + 1; i++) {

            for (int j = 1; j < N + 1; j++) {

                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + A[i-1][j-1];

            }

        } 

        for (int i1 = 0; i1 < M; i1++) {

            for (int i2 = i1+1; i2 < M+1; i2++) {

                // region init

                int min1 = 0; // minimum value of a rectangle [i1..i2-1]x[0..j-1]

                int minJ1 = 0; // minimum for such j when minimum in one dimension using a formula like that for sum but in one dimension

                // sum'[j] = sum[i2 + 1][j] - sum[i1][j]

                int maxValue1 = 0; // maximum value of a rectangle [i1..i2-1]x[j'..j-1]

                int max1 = 0; // maximum value of a rectangle [i1..i2-1]x[0..j-1]

                int maxJ1 = 0; // minimum such j

 

                int minCost1 = 0; // minimum value of a rectangle [i1..i2-1]x[j'..j-1]

                int min2 = 0; // minimum value of a rectangle [0..i1-1, i2..M-1] x [0..j-1]

                int minJ2 = 0; // maximum such j

 

                int maxValue2 = 0; // maximum value of a rectangle [0..i1-1, i2..M-1] x [j'..j-1]

                int max2 = 0; // maximum value of a rectangle [0..i1-1, i2..M-1] x [0..j-1]

                int maxJ2 = 0; // minimum such j

 

                int minCost2 = 0; // minimum value of a rectangle [0..i1-1, i2..M-1] x [j'..j-1]

                // endregion init

                for (int j = 1; j < N+1; j++) {

                    int value1 = sum[i2][j] - sum[i1][j];

                    min1 = Math.min(value1, min1);

                    minJ1 = (value1 == min1)? j : minJ1;

                    maxValue1 = Math.max(value1 - min1, maxValue1);

                    max1 = Math.max(max1, value1);

                    maxJ1 = (max1 == value1) ? j : maxJ1;

                    minCost1 = Math.min(minCost1, value1 - max1);

                    int value2 = sum[M][j] - value1;

                    min2 = Math.min(min2, value2);

                    minJ2 = (min2 == value2) ? j : minJ2;

                    maxValue2 = Math.max(maxValue2, value2 - min2);

                    max2 = Math.max(value2, max2);

                    maxJ2 = (max2 == value2)  ? j : maxJ2;

                    minCost2 = Math.min(minCost2, value2 - max2);

                    result = Arrays.asList(result, maxValue1, maxValue2, value1 - minCost1, value2 - minCost2).stream().mapToInt(x -> x).max().getAsInt();

                }

            }

        }

        return result;

    }

    public static void main(String[] args) { 

        int[][] A = new int[2][2]; 

        A[0][0] = 1; 

        A[0][1] = 1; 

        A[1][0] = 1; 

        A[1][1] = 0; 

        System.out.println(getMax(A)); 

} 

3 // output