MaxSum sub matrix within a matrix
The begin returned by maxSubArraySub can be wrong as we update start after we've found a good candidate for the maximal sum. This can lead to potential bugs (I am way too lazy to find an actual case where it makes a difference but that should be possible). The solution from http://en.wikipedia.org/wiki/Maximum_subarray_problem introduces another variable to have a temporary starting point and one for the actual starting point of the maximum found so far.

You can make things much simpler by defining (very simple) classes for 3-tuple and 4-tuple. Make the members private and final and you won't need getters. As the point is just to return multiple values from a function, I don't think there a point in making things too specific and I'd rather have the class and the members have simple names.

You have a typo in your class name and it's especially annoying in Java where the file name has to match ;-)

You could make your code a bit more robust by asserting that all rows have same length.

In your code, the comment about complexity is wrong. The one is your stackoverflow question is right, it is indeed N*N*M :-)

Here's what I've done :

final class Tuple4 {
    public final int a;
    public final int b;
    public final int c;
    public final int d;

    public Tuple4(int a, int b, int c, int d) {
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }
}

final class Tuple3 {
    public final int a;
    public final int b;
    public final int c;

    public Tuple3(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

/**
 * Returns the maximum rectangle in the matrix
 *
 * @author javadeveloper
 */
public final class MaximumSumRectangleInMatrix {

    // made this utility class non-instantiable
    private MaximumSumRectangleInMatrix() { }

    private static Tuple3 maxSubArraySum(int[] a) {
        assert a != null &amp;&amp; a.length &gt; 0;

        int max = a[0];
        int currSum = a[0];

        int start = 0;
        int start_tmp = 0;
        int end = 0;

        for (int i = 1; i &lt; a.length; i++) {
            if (currSum &lt; 0) {
                start_tmp = i;
                currSum = a[i];
            } else {
                currSum += a[i];
            }
            if (currSum &gt; max) {
                max = currSum;
                start = start_tmp;
                end = i;
            }
        }
        return new Tuple3(start, end, max);
    }


    /**
     * Returns the Tuple4 object containing the maximum
     * rectangle in the matrix.
     *
     * @param  The input matrix.
     * @return The rectanglecoor object containing the coordinates of the maximum sub matrix
     */
    public static Tuple4 calMaxRectangle(int[][] m) {
        if (m.length == 0 || m[0].length == 0) {
            throw new IllegalArgumentException("The matrix should be non empty");
        }

        int max = Integer.MIN_VALUE;
        int a = 0;
        int b = 0;
        int c = 0;
        int d = 0;

        int lengthRow = m[0].length;

        for (int i1 = 0; i1 &lt; m.length; i1++)
        {
            if (lengthRow != m[i1].length)
                throw new IllegalArgumentException("Matrix is not square");

            int[] temp = new int[lengthRow];
            for (int i2 = i1; i2 &lt; m.length; i2++)
            {
                for (int j = 0; j &lt; lengthRow; j++)
                    temp[j] += m[i2][j];

                Tuple3 maxSubArrayCoord = maxSubArraySum(temp);

                if (maxSubArrayCoord.c &gt; max) {
                    max = maxSubArrayCoord.c;
                    a = i1;
                    b = maxSubArrayCoord.a;
                    c = i2;
                    d = maxSubArrayCoord.b;
                }
            }
        }
        return new Tuple4(a,b,c,d);
    }

    public static void main(String[] args) {
        int[][] m = {  {-20, -30, -40, -50,  50},
                       { 10,  20,  30,  50, -10},
                       { 50,  60,  70,  80,  30},
                       {-10, -20, -30, -40,  60},
                    };

        Tuple4 r = calMaxRectangle(m);
        System.out.println("(" + r.a + "," + r.b + ") ; (" + r.c + "," + r.d + ")");
    }
}