Kadane's Algorithm for Maximum Submatrix Sum

Maximum subarray sum and maximum submatrix sum are common dynamic programming problems in many programming contests.

In this tutorial, I will show you how to solve the maximum submatrix sum problem using Kadane's Algorithm.

I will also explain the intuition behind Kadane's Algorithm and provide code implementations in C++, JavaScript, and Python.

What is Kadane's Algorithm?
Kadane's Algorithm for 1D Array
Kadane's Algorithm for 2D Matrix
- How the 2D Kadane's Algorithm Works
- Example of Kadane's Algorithm for 2D Matrices
Code Implementation of Kadane's Algorithm for 1D Array
Code Implementation of Kadane's Algorithm for 2D Matrix
Conclusion

What is Kadane's Algorithm?

Kadane's Algorithm is a dynamic programming algorithm that is used to find the maximum sum of a subarray in a 1D array and can be extended to 2D matrices (which I will explain later).

The algorithm is named after its inventor, Jay Kadane, who developed it in 1984. Until now, it is still a common algorithm that appears in a lot of programming problems.

The problem is given below. Consider the example matrix in the image and its green submatrix with a total sum of 15 (and also the maximum sum of all submatrices in the example matrix).

How do we find that green matrix? That's where Kadane's Algorithm comes in.

Kadane's Algorithm for 1D Array

Before diving into Kadane's Algorithm for 2D matrices, let's first look at how it works for 1D arrays.

Kadane’s algorithm is commonly used to find the maximum subarray sum in a 1D array in O(n) time complexity.

Problem: Given an array of integers, find the maximum sum of a subarray.

Example: Given the array [2, 1, 0, 3, -4, 5], the maximum sum of a subarray is 7, which is the sum of the subarray [0, 3, -4, 5].

Steps to Solve:

Create the sum variable to store the sum of the current subarray and initialize it to 0.
Create the ans variable to store the maximum sum of a subarray and initialize it to 0.
Iterate through the array and add each element to the sum variable.
If the sum variable is greater than the ans variable, update the ans variable.
If the sum variable is less than 0, reset it to 0.
Return the ans variable.

kadanes-algorithm-1d.cpp


#include <iostream>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
 
    int sum = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (sum > ans) ans = sum;
        if (sum < 0) sum = 0;
    }
    cout << ans;
    return 0;
}

Kadane's Algorithm for 2D Matrix

Now let's look at how Kadane's Algorithm can be extended to 2D matrices.

How the 2D Kadane's Algorithm Works

The idea for 2D matrices is similar to 1D arrays.

For each pair of columns i and j, and with each row k, we can take the sum of all elements in row k between columns i and j.
This will give us a 1D array for each pair of columns i and j:
- sum[0] = a[0][i] + a[0][i + 1] + ... + a[0][j]
- sum[1] = a[1][i] + a[1][i + 1] + ... + a[1][j]
- ...
- sum[n - 1] = a[n - 1][i] + a[n - 1][i + 1] + ... + a[n - 1][j]
Then, we can apply Kadane's Algorithm to find the maximum sum of a subarray in each of these 1D arrays.
Finally, we can take the maximum of all these sums to get the maximum sum of a submatrix.

Step 1 takes O(nm) time. Step 2 takes O(n) time as we can use prefix sum to calculate the sum of each row in O(1) time. In overall, the time complexity of Kadane's Algorithm for 2D matrices is O(nm²).

Here is the code in C++:

kadanes-algorithm-2d.cpp


// Calculate prefix sum
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> a[i][j];
        if (j > 0) a[i][j] += a[i][j - 1]; // prefix sum for i-th row
    }
}
// Kadane's algorithm for 2D array
int ans = 0;
for (int i = 0; i < m; i++) { // from i
    for (int j = i + 1; j < m; j++) { // to j
        int sum = 0;
        for (int k = 0; k < n; k++) { // iterate from first row to last row
            sum += a[k][j];
            if (i > 0) sum -= a[k][i - 1];
            if (sum > ans) ans = sum;
            if (sum < 0) sum = 0;
        }
    }
}

Example of Kadane's Algorithm for 2D Matrices

Suppose we have the following 2D matrix:

console


 1   2  -1  -4 -20
-8  -3   4   2   1
 3   8  10   1   3
-4  -1   1   7  -6

Our goal is to find the maximum sum of a rectangular submatrix. Here's how we can apply Kadane's Algorithm to solve this problem:

First, we calculate the prefix sum for each row of the matrix. This gives us the following matrix:

text


 1   3   2  -2 -22
-8 -11  -7  -5  -4
 3  11  21  22  25
-4  -5  -4   3  -3

Next, we iterate through all possible pairs of columns (i, j) and apply Kadane's Algorithm to the subarray between columns i and j. For example, when i=0 and j=2, the subarray looks like this:
text
```
 1   2  -1
-8  -3   4
 3   8  10
-4  -1   1
```
We apply Kadane's Algorithm to this subarray, starting with an empty subarray and accumulating elements until the sum becomes negative. When the sum is negative, we reset it to 0 and continue accumulating. At each step, we keep track of the maximum sum we have seen so far. Applying Kadane's Algorithm to the subarray above, we get a maximum sum of 21.
We repeat this process for all pairs of columns and keep track of the maximum sum we find. In this case, the maximum sum is 29, which occurs in the submatrix:
text
```
10  1   3
 1  7  -6
```

Overall, Kadane's Algorithm allows us to efficiently find the maximum sum of a rectangular submatrix in a 2D matrix.

Code Implementation of Kadane's Algorithm for 1D Array

C++ (1D Array)

kadanes-algorithm-1d.cpp


#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n; cin >> n;
    vector<int> a(n);
 
    for(int i = 0; i < n; i++) cin >> a[i];
    int sum = 0, ans = 0;
    for(int i = 0; i < n; i++){
        sum += a[i];
        ans = max(ans, sum);
        if (sum < 0) sum = 0;
    }
    cout << ans;
    return 0;
}

JavaScript (1D Array)

kadanes-algorithm-1d.js


function kadanesAlgorithm(arr) {
  let currentSum = 0;
  let maxSum = -Infinity;
 
  for (let i = 0; i < arr.length; i++) {
    currentSum = Math.max(currentSum + arr[i], arr[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
 
  return maxSum;
}

Python (1D Array)

kadanes-algorithm-1d.py


def kadanes_algorithm(arr):
    current_sum = 0
    max_sum = float('-inf')
 
    for num in arr:
        current_sum = max(current_sum + num, num)
        max_sum = max(max_sum, current_sum)
 
    return max_sum

Code Implementation of Kadane's Algorithm for 2D Matrix

C++ (2D Matrix)

kandanes-algorithm-2d.cpp


#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int> > a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (j > 0) a[i][j] += a[i][j - 1]; // prefix sum for i-th row
        }
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            int sum = 0;
            for (int k = 0; k < n; k++) { // iterate from first row
                sum += a[k][j];
                if (i > 0) sum -= a[k][i - 1];
                ans = max(ans, sum);
                if (sum < 0) sum = 0;
            }
        }
    }
    cout << ans;
    return 0;
}

JavaScript (2D Matrix)

kadanes-algorithm-2d.js


function kadanesAlgorithm2D(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let maxSum = -Infinity;
 
  for (let left = 0; left < cols; left++) {
    const rowSums = new Array(rows).fill(0);
 
    for (let right = left; right < cols; right++) {
      for (let i = 0; i < rows; i++) {
        rowSums[i] += matrix[i][right];
      }
 
      let currentSum = 0;
      let maxEndingHere = -Infinity;
 
      for (let i = 0; i < rows; i++) {
        currentSum += rowSums[i];
        maxEndingHere = Math.max(maxEndingHere + rowSums[i], rowSums[i]);
        maxSum = Math.max(maxSum, maxEndingHere, currentSum);
      }
    }
  }
 
  return maxSum;
}

Python (2D Matrix)

kadanes-algorithm-2d.py


def kadanes_algorithm_2d(matrix):
    rows, cols = len(matrix), len(matrix[0])
    max_sum = float('-inf')
 
    for left in range(cols):
        row_sums = [0] * rows
 
        for right in range(left, cols):
            for i in range(rows):
                row_sums[i] += matrix[i][right]
 
            current_sum = 0
            max_ending_here = float('-inf')
 
            for i in range(rows):
                current_sum += row_sums[i]
                max_ending_here = max(max_ending_here + row_sums[i], row_sums[i])
                max_sum = max(max_sum, max_ending_here, current_sum)
 
    return max_sum

Conclusion

Kadane's algorithm is a powerful tool for finding the maximum sum of subarrays in 1D arrays and 2D matrices.

Its time complexity of O(n) for 1D arrays and O(nm²) for 2D matrices make it an efficient solution to many programming problems.

Kadane's Algorithm for Maximum Submatrix Sum

Contents

What is Kadane's Algorithm?

Kadane's Algorithm for 1D Array

Kadane's Algorithm for 2D Matrix

How the 2D Kadane's Algorithm Works

Example of Kadane's Algorithm for 2D Matrices

Code Implementation of Kadane's Algorithm for 1D Array

C++ (1D Array)

JavaScript (1D Array)

Python (1D Array)

Code Implementation of Kadane's Algorithm for 2D Matrix

C++ (2D Matrix)

JavaScript (2D Matrix)

Python (2D Matrix)

Conclusion

Contents

What is Kadane's Algorithm?

Kadane's Algorithm for 1D Array

Kadane's Algorithm for 2D Matrix

How the 2D Kadane's Algorithm Works

Example of Kadane's Algorithm for 2D Matrices

Code Implementation of Kadane's Algorithm for 1D Array

C++ (1D Array)

JavaScript (1D Array)

Python (1D Array)

Code Implementation of Kadane's Algorithm for 2D Matrix

C++ (2D Matrix)

JavaScript (2D Matrix)

Python (2D Matrix)

Conclusion

Most Read