Arrays January 20 ,2026

Maximum Sum Submatrix

(Kadane’s Algorithm on 2D Matrix)

Problem Statement

You are given a 2D matrix mat of size R x C containing positive and negative integers.

Your task is to find the maximum sum of any rectangular submatrix.

Example

Input

mat = [
  [ 1,  2, -1, -4, -20],
  [-8, -3,  4,  2,   1],
  [ 3,  8, 10,  1,   3],
  [-4, -1,  1,  7,  -6]
]

Output

Explanation

Maximum sum submatrix is:

[
  [-3,  4, 2],
  [ 8, 10, 1],
  [-1, 1, 7]
]

Sum = 29

Why This Problem Is Important

Classic 2D Kadane’s Algorithm
Frequently asked in Google, Amazon, Microsoft
Tests:
- Matrix compression
- Optimal subarray logic
Foundation for 2D DP & advanced matrix problems

Approaches Overview

Approach	Technique	Time	Space
Approach 1	Brute Force (All rectangles)	O(R²·C²)	O(1)
Approach 2	Prefix Sum (2D)	O(R²·C²)	O(R·C)
Approach 3	Kadane’s on Columns (Optimal)	O(C²·R)	O(R)

Approach 1: Brute Force

Idea

Try all possible rectangles
Compute sum cell by cell

Time & Space

Time: O(R²·C²)
Space: O(1)

Implementations

C

#include 
#include 

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };
    int R = 4, C = 5;
    int maxSum = INT_MIN;

    for(int r1=0;r1 maxSum) maxSum = sum;
                }

    printf("%d", maxSum);
}

C++

#include 
using namespace std;

int main() {
    vector> mat = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };
    int R = mat.size(), C = mat[0].size();
    int maxSum = INT_MIN;

    for(int r1=0;r1

Java

class MaxSumSubmatrix {
    public static void main(String[] args) {
        int[][] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };
        int R = mat.length, C = mat[0].length;
        int maxSum = Integer.MIN_VALUE;

        for(int r1=0;r1

Python

mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
]

R, C = len(mat), len(mat[0])
maxSum = float('-inf')

for r1 in range(R):
    for c1 in range(C):
        for r2 in range(r1, R):
            for c2 in range(c1, C):
                s = 0
                for i in range(r1, r2+1):
                    for j in range(c1, c2+1):
                        s += mat[i][j]
                maxSum = max(maxSum, s)

print(maxSum)

JavaScript

let mat = [
  [1,2,-1,-4,-20],
  [-8,-3,4,2,1],
  [3,8,10,1,3],
  [-4,-1,1,7,-6]
];

let R = mat.length, C = mat[0].length;
let maxSum = -Infinity;

for(let r1=0;r1

C#

using System;

class Program {
    static void Main() {
        int[,] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = 4, C = 5;
        int maxSum = int.MinValue;

        for(int r1=0;r1

Output

Approach 2: Prefix Sum (2D)

Idea

Build a 2D prefix sum matrix
Rectangle sum in O(1)
Enumerate all rectangles

Time & Space

Time: O(R² · C²)
Space: O(R · C)

Implementations

C

#include 
#include 

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };
    int R = 4, C = 5;
    int ps[5][6] = {0};

    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
            ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];

    int maxSum = INT_MIN;

    for(int r1=1;r1<=R;r1++)
        for(int c1=1;c1<=C;c1++)
            for(int r2=r1;r2<=R;r2++)
                for(int c2=c1;c2<=C;c2++) {
                    int sum = ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1];
                    if(sum > maxSum) maxSum = sum;
                }

    printf("%d", maxSum);
}

C++

#include 
using namespace std;

int main() {
    vector> mat = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = mat.size(), C = mat[0].size();
    vector> ps(R+1, vector(C+1,0));

    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
            ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];

    int maxSum = INT_MIN;

    for(int r1=1;r1<=R;r1++)
        for(int c1=1;c1<=C;c1++)
            for(int r2=r1;r2<=R;r2++)
                for(int c2=c1;c2<=C;c2++) {
                    int sum = ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1];
                    maxSum = max(maxSum, sum);
                }

    cout << maxSum;
}

Java

class MaxSumSubmatrix {
    public static void main(String[] args) {
        int[][] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = mat.length, C = mat[0].length;
        int[][] ps = new int[R+1][C+1];

        for(int i=1;i<=R;i++)
            for(int j=1;j<=C;j++)
                ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];

        int maxSum = Integer.MIN_VALUE;

        for(int r1=1;r1<=R;r1++)
            for(int c1=1;c1<=C;c1++)
                for(int r2=r1;r2<=R;r2++)
                    for(int c2=c1;c2<=C;c2++) {
                        int sum = ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1];
                        maxSum = Math.max(maxSum, sum);
                    }

        System.out.println(maxSum);
    }
}

Python

mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
]

R, C = len(mat), len(mat[0])
ps = [[0]*(C+1) for _ in range(R+1)]

for i in range(1, R+1):
    for j in range(1, C+1):
        ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1]

maxSum = float('-inf')

for r1 in range(1, R+1):
    for c1 in range(1, C+1):
        for r2 in range(r1, R+1):
            for c2 in range(c1, C+1):
                s = ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1]
                maxSum = max(maxSum, s)

print(maxSum)

JavaScript

let mat = [
  [1,2,-1,-4,-20],
  [-8,-3,4,2,1],
  [3,8,10,1,3],
  [-4,-1,1,7,-6]
];

let R = mat.length, C = mat[0].length;
let ps = Array.from({length:R+1},()=>Array(C+1).fill(0));

for(let i=1;i<=R;i++)
  for(let j=1;j<=C;j++)
    ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];

let maxSum = -Infinity;

for(let r1=1;r1<=R;r1++)
  for(let c1=1;c1<=C;c1++)
    for(let r2=r1;r2<=R;r2++)
      for(let c2=c1;c2<=C;c2++){
        let sum = ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1];
        maxSum = Math.max(maxSum, sum);
      }

console.log(maxSum);

C#

using System;

class Program {
    static void Main() {
        int[,] mat = {
            {1,2,-1,-4,-20},
            {-8,-3,4,2,1},
            {3,8,10,1,3},
            {-4,-1,1,7,-6}
        };

        int R = 4, C = 5;
        int[,] ps = new int[R+1, C+1];

        for(int i=1;i<=R;i++)
            for(int j=1;j<=C;j++)
                ps[i,j] = mat[i-1,j-1] + ps[i-1,j] + ps[i,j-1] - ps[i-1,j-1];

        int maxSum = int.MinValue;

        for(int r1=1;r1<=R;r1++)
            for(int c1=1;c1<=C;c1++)
                for(int r2=r1;r2<=R;r2++)
                    for(int c2=c1;c2<=C;c2++) {
                        int sum = ps[r2,c2] - ps[r1-1,c2] - ps[r2,c1-1] + ps[r1-1,c1-1];
                        maxSum = Math.Max(maxSum, sum);
                    }

        Console.WriteLine(maxSum);
    }
}

Output

Approach 3: Kadane’s Algorithm (Optimal)

Idea

Fix left & right columns
Compress rows → 1D array
Apply Kadane’s Algorithm

Time & Space

Time: O(C² · R)
Space: O(R)

Implementations

C

#include 
#include 

int kadane(int arr[], int n) {
    int maxSum = arr[0], curr = arr[0];
    for(int i=1;i arr[i] ? curr + arr[i] : arr[i];
        maxSum = maxSum > curr ? maxSum : curr;
    }
    return maxSum;
}

int main() {
    int mat[4][5] = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = 4, C = 5;
    int maxSum = INT_MIN;

    for(int left=0; left maxSum) maxSum = sum;
        }
    }

    printf("%d", maxSum);
}

C++

#include 
using namespace std;

int kadane(vector& arr) {
    int maxSum = arr[0], curr = arr[0];
    for(int i=1;i> mat = {
        {1,2,-1,-4,-20},
        {-8,-3,4,2,1},
        {3,8,10,1,3},
        {-4,-1,1,7,-6}
    };

    int R = mat.size(), C = mat[0].size();
    int maxSum = INT_MIN;

    for(int left=0; left temp(R,0);
        for(int right=left; right

Java

class MaxSumSubmatrix {
    static int kadane(int[] arr) {
        int maxSum = arr[0], curr = arr[0];
        for(int i=1;i

Python

def kadane(arr):
    max_sum = curr = arr[0]
    for x in arr[1:]:
        curr = max(x, curr + x)
        max_sum = max(max_sum, curr)
    return max_sum

mat = [
    [1,2,-1,-4,-20],
    [-8,-3,4,2,1],
    [3,8,10,1,3],
    [-4,-1,1,7,-6]
]

R, C = len(mat), len(mat[0])
maxSum = float('-inf')

for left in range(C):
    temp = [0]*R
    for right in range(left, C):
        for i in range(R):
            temp[i] += mat[i][right]
        maxSum = max(maxSum, kadane(temp))

print(maxSum)

JavaScript

function kadane(arr){
  let maxSum = arr[0], curr = arr[0];
  for(let i=1;i

C#

using System;

class Program {
    static int Kadane(int[] arr) {
        int maxSum = arr[0], curr = arr[0];
        for(int i=1;i

Output

Summary

Brute Force: Concept clarity
Prefix Sum: Rectangle optimization
Kadane’s 2D: Interview favorite
Handles negative numbers
Essential for advanced matrix DP

Next Problem in the Series

Count Subarrays with XOR Equal to K

Sanjiv

You must logged in to post comments.

Data Structure

Data Structure

Table of Contents

Maximum Sum Submatrix

Problem Statement

Example

Input

Output

Explanation

Why This Problem Is Important

Approaches Overview

Approach 1: Brute Force

Idea

Time & Space

Implementations

C

C++

Java

Python

JavaScript

C#

Approach 2: Prefix Sum (2D)

Idea

Time & Space

Implementations

C

C++

Java

Python

JavaScript

C#

Approach 3: Kadane’s Algorithm (Optimal)

Idea

Time & Space

Implementations

C

C++

Java

Python

JavaScript

C#

Summary

Next Problem in the Series

Related Blogs

Find the Second Smal...

Array Data Structure

Array Memory Represe...

Array Operations and...

Advantages and Disad...

Arrays in C

Vector in C++ STL

Arrays vs ArrayList...

JavaScript Arrays

Binary Search on Arr...

Two Pointers Techniq...

Prefix Sum Technique

Sliding Window Techn...

Basics of Hashing fo...

Traverse an Array

Find the Sum of All...

Find the Maximum Ele...

Find the Minimum Ele...

Count Even and Odd N...

Search an Element in...

Copy One Array into...

Reverse an Array

Print Alternate Elem...

Find the Length of a...

Check if an Array is...

Find the First Eleme...

Find the Last Elemen...

Count the Number of...

Replace All Elements...

Sum of Elements at E...

Sum of Elements at O...

Find the Average of...

Print Array Elements...

Count the Number of...

Remove Duplicate Ele...

Move All Zeros to th...