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.
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 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
sumfrom the first element of the array.
- If the
sumbecomes negative, reset it to
- Keep track of the maximum sum we have seen so far.
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(m2), while applying Kadane's Algorithm takes O(n) time. Thus, the total time complexity is O(nm2) or O(n3) for square matrices. Here's the code:
Suppose we have the following 2D matrix:
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
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
j=2, the subarray looks like this:text
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
Overall, Kadane's Algorithm allows us to efficiently find the maximum sum of a rectangular submatrix in a 2D matrix.
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.
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(nm2) 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.