Kadane's Algorithm for Maximum Submatrix Sum

The optimal algorithm to find the maximum subarray sum in 1D arrays and 2D matrices is the Kadane's Algorithm.

The problem is given as below, consider the example matrix in the image, which has the maximum submatrix sum with a total value of 15. How do we find that?

That's where Kadane's Algorithm comes in.

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.

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

Kadane's Algorithm for 1D Array

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

Here are the steps:

Start accumulating the sum from the first element of the array.
If the sum becomes negative, reset it to 0.
Keep track of the maximum sum we have seen so far.

kadanes-algorithm-1d.cpp

int sum = 0, ans = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];
    ans = max(ans, sum);
    if (sum < 0) sum = 0;
}

Kadane's Algorithm for 2D Matrix

To apply Kadane's Algorithm to a 2D array, we can fix two columns and consider every row between them as elements in a 1D array. By calculating the prefix sum, we can efficiently determine the maximum subarray in the 1D array using Kadane's Algorithm. The time complexity for fixing two columns is O(m²), while applying Kadane's Algorithm takes O(n) time. Thus, the total time complexity is O(nm²) or O(n³) for square matrices. Here's the code:

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++) { // fix i
    for (int j = i + 1; j < m; j++) { // fix 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];
            ans = max(ans, sum);
            if (sum < 0) sum = 0;
        }
    }
}

Example of Kadane's Algorithm for 2D Matrices

Suppose we have the following 2D matrix:

shell

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.

Practical Applications of Kadane's Algorithm for 2D Matrices

Kadane's Algorithm for 2D Matrices has several practical applications in various fields. In image processing, for example, it can be used to find the maximum sum of a rectangular submatrix of pixel values. This can be useful in identifying important regions of an image, such as in object detection or facial recognition.

In finance, Kadane's Algorithm can be used to find the maximum return on investment within a given time period. By representing the values of different investment options in a 2D matrix, the algorithm can efficiently identify the combination of investments that yields the highest return.

Overall, Kadane's Algorithm for 2D matrices has broad applicability and can be used in a variety of contexts where optimization problems involving rectangular submatrices arise.

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++) { // fix i
        for (int j = i + 1; j < m; j++) { // fix 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. The algorithm is easy to implement and requires only a few lines of code. By understanding the intuition behind Kadane's algorithm, you can apply it to solve various types of problems.