Maximum sum Rectangle

Intuition

Extend Kadane algorithm to 2D. Fix left and right column boundaries, compress rows into 1D array using prefix sums, then apply Kadane on the 1D array.

Algorithm

1Fix left col l from 0 to n-1.
2For each l, scan right col r from l to n-1: accumulate column sums into 1D temp array.
3Apply Kadane on temp to find max subarray sum.

Example Walkthrough

Input: 4x5 matrix

1.Fix l=1,r=3. Column sums form 1D array. Kadane finds max subarray.

Output: Max sum rectangle

Common Pitfalls

•Time O(n^2 * m). Track row boundaries by storing start/end in Kadane.

Maximum sum Rectangle.java

Java

// Approach: Fix left and right columns; compress to 1D using column sums, then apply Kadane's.
// Time: O(n^2 * m) Space: O(n)
class Solution {
    public int maxRectSum(int M[][]) {
        int R = M.length;
        int C = M[0].length;
        int maxSum = Integer.MIN_VALUE;

        for (int left = 0; left < C; left++) {
            int[] temp = new int[R];

            for (int right = left; right < C; right++) {
                for (int i = 0; i < R; i++)
                    temp[i] += M[i][right];

                int currentMax = kadane(temp);
                maxSum = Math.max(maxSum, currentMax);
            }
        }

        return maxSum;
    }

    private int kadane(int[] arr) {
        int maxEndingHere = arr[0];
        int maxSoFar = arr[0];

        for (int i = 1; i < arr.length; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }
};

Was this solution helpful?