Maximum Submatrix

Updated at September 26, 2025

1 min read

Want to edit

#data-structures

Content Reader1 words • 0:00 • Browser TTS

Maximum Submatrix

Problem Statement:

Find the submatrix with maximum sum in a 2D array.

Approach:

Fix left and right columns, apply Kadane's on compressed rows.

Time Complexity:

Time = O(N²×M), Space = O(N)

JavaScript Code:

function maxSubmatrix(A) {
    const N = A.length, M = A[0].length;
    let maxSum = -Infinity;
    
    for (let left = 0; left < M; left++) {
        const temp = new Array(N).fill(0);
        
        for (let right = left; right < M; right++) {
            for (let i = 0; i < N; i++) {
                temp[i] += A[i][right];
            }
            
            // Apply Kadane's on temp
            let currentSum = temp[0];
            let maxKadane = temp[0];
            for (let i = 1; i < N; i++) {
                currentSum = Math.max(temp[i], currentSum + temp[i]);
                maxKadane = Math.max(maxKadane, currentSum);
            }
            
            maxSum = Math.max(maxSum, maxKadane);
        }
    }
    
    return maxSum;
}