current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

Code review for best practices, optimizations, code cleanup etc. Also requesting verification of the complexity: O(row*row*col).

/**
 * Contains coordinates of the 
 * topMost left, of matrix, obtained by getRowOne and colRowOne
 * bottomMost right, of matrix, obtained by getRowTwo and getColTwo
 * 
 * @author javadeveloper
 */
final class RectangleCoord {
    private final int rowOne;
    private final int colOne;
    private final int rowTwo;
    private final int colTwo;

    public RectangleCoord(int rowOne, int colOne, int rowTwo, int colTwo) {
        this.rowOne = rowOne;
        this.colOne = colOne;
        this.rowTwo = rowTwo;
        this.colTwo = colTwo;
    }

    public int getRowOne() { 
        return rowOne;
    }

    public int getColOne() {
        return colOne;
    }

    public int getRowTwo() {
        return rowTwo;
    }

    public int getColTwo() {
        return colTwo;
    }
}


/**
 * Returns the maximum rectangle in the matrix
 * 
 * Complexity:
 *  O(row2 * col)
 *
 * @author javadeveloper
 */
public final class MaximumSumRectangeInMatrix {

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


    private static class MaxSubArray {
        int start;
        int end;
        int maxSum;

        public MaxSubArray(int start, int end, int maxSum) {
            this.start = start;
            this.end = end;
            this.maxSum = maxSum;
        }
    }

    private static MaxSubArray maxSubArraySum(int[] a) {
        assert a != null && a.length > 0; 

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

        int start = 0;
        int end = 0;

        for (int i = 1; i < a.length; i++) {
            currSum = currSum + a[i];
            if (a[i] > currSum) {
                start = i;
                currSum = a[i];
            }
            if (currSum > max) {
                max = currSum;
                end = i;
            }
        }
        return new MaxSubArray(start, end, max);
    }


    /**
     * Returns the RectangleCoord 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 RectangleCoord 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 rowOne = 0;
        int colOne = 0;
        int rowTwo = 0;
        int colTwo = 0;

        for (int fromRow = 0; fromRow < m.length; fromRow++) {
            int[] temp = new int[m[0].length];
            for (int toRow = fromRow; toRow < m.length; toRow++) {
                for (int col = 0; col < m[0].length; col++) {
                    temp[col] = temp[col] + m[toRow][col];
                }

                MaxSubArray maxSubArrayCoord = maxSubArraySum(temp);

                if (maxSubArrayCoord.maxSum > max) {
                    max = maxSubArrayCoord.maxSum;
                    rowOne = fromRow;
                    colOne = maxSubArrayCoord.start;
                    rowTwo = toRow;
                    colTwo = maxSubArrayCoord.end;
                }
            }
        }

        return new RectangleCoord(rowOne, colOne, rowTwo, colTwo);
    }

    public static void main(String[] args) {


        int[][] m = {  {-20, -30, -40, -50},
                       { 10,  20,  30,  50},
                       { 50,  60,  70,  80},
                       {-10, -20, -30, -40},
                    };

        RectangleCoord r = calMaxRectangle(m);
        System.out.println(r.getRowOne() + " : " + r.getColOne());
        System.out.println(r.getRowTwo() + " : " + r.getColTwo());

    }

}
share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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 && a.length > 0;

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

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

        for (int i = 1; i < a.length; i++) {
            if (currSum < 0) {
                start_tmp = i;
                currSum = a[i];
            } else {
                currSum += a[i];
            }
            if (currSum > 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 < 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 < m.length; i2++)
            {
                for (int j = 0; j < lengthRow; j++)
                    temp[j] += m[i2][j];

                Tuple3 maxSubArrayCoord = maxSubArraySum(temp);

                if (maxSubArrayCoord.c > 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 + ")");
    }
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.