Introduction
Kadane's algorithm is a dynamic programming algorithm used for solving a variety of problems related to arrays. It was proposed by Jay Kadane in 1984 and is widely used due to its simplicity and efficiency. In this blog post, we will explore how Kadane's algorithm works and list some of the problems that can be solved using it.
Kadane's Algorithm
Kadane's algorithm is used to find the maximum sum subarray of a given array. The maximum sum subarray is defined as the contiguous subarray within an array that has the largest sum. For example, in the array `[1, -2, 3, 4, -5, 6]`, the maximum sum subarray is `[3, 4, -5, 6]`.
The algorithm works by iterating over the array and keeping track of the maximum sum seen so far. At each step, the algorithm computes the maximum sum of all subarrays that end at the current element. The maximum sum of all subarrays that end at the current element is either the current element itself or the sum of the current element and the maximum sum of all subarrays that end at the previous element.
Algorithm in pseudocode
Here's the algorithm in pseudocode:
In this algorithm, `array` is the input array, `n` is the length of the array, `max_sum_so_far` is the maximum sum seen so far, `max_sum_ending_here` is the maximum sum of all subarrays that end at the current element, and `max` is a function that returns the maximum of two integers.
Algorithm working
The algorithm works as follows:
1. We initialize `max_sum_so_far` and `max_sum_ending_here` to 0.
2. We iterate over the `array` array, from the first element to the last element. For each element, we compute the maximum sum of all subarrays that end at the current element.
3. We update `max_sum_ending_here` to be the maximum of 0 and `max_sum_ending_here + array[i]`. This ensures that `max_sum_ending_here` always represents the maximum sum of all subarrays that end at the current element.
4. We update `max_sum_so_far` to be the maximum of `max_sum_so_far` and `max_sum_ending_here`. This ensures that `max_sum_so_far` always represents the maximum sum seen so far.
5. We return `max_sum_so_far` as the result.
Problems Solved by Kadane's Algorithm
Kadane's algorithm can be used to solve a variety of problems related to arrays. Here are some of the problems that can be solved using Kadane's algorithm:
1. Maximum Subarray
As discussed earlier, Kadane's algorithm can be used to find the maximum sum subarray of a given array.
2. Maximum Product Subarray
Kadane's algorithm can also be used to find the maximum product subarray of a given array. The maximum product subarray is defined as the contiguous subarray within an array that has the largest product.
The algorithm for finding the maximum product subarray is similar to Kadane's algorithm for finding the maximum sum subarray. The only difference is that we keep track of the maximum product seen so far instead of the maximum sum seen so far.
3. Maximum Sum Circular Subarray
Kadane's algorithm can be used to find the maximum sum circular subarray of a given array. The maximum sum circular subarray is defined as the contiguous subarray within an array that has the largest sum, considering the array to be circular.
To find the maximum sum circular subarray, we first find the maximum sum subarray using Kadane's algorithm. We then find the minimum sum subarray using the same algorithm. The maximum sum circular subarray is the maximum of the maximum sum subarray and the sum of the array minus the minimum sum subarray.
4. Maximum Sum Subsequence
Kadane's algorithm can also be used to find the maximum sum subsequence of a given array. The maximum sum subsequence is defined as the non-contiguous subsequence within an array that has the largest sum.
To find the maximum sum subsequence, we initialize `max_sum_so_far` and `max_sum_ending_here` to the first element of the array. We then iterate over the remaining elements of the array and update `max_sum_ending_here` to be the maximum of the current element and the sumof the current element and `max_sum_ending_here`. We update `max_sum_so_far` to be the maximum of `max_sum_so_far` and `max_sum_ending_here`. Finally, we return `max_sum_so_far` as the result.
5. Minimum Sum Subarray
Kadane's algorithm can also be used to find the minimum sum subarray of a given array. The minimum sum subarray is defined as the contiguous subarray within an array that has the smallest sum.
To find the minimum sum subarray, we can modify Kadane's algorithm to keep track of the minimum sum seen so far instead of the maximum sum seen so far. The algorithm works as follows:
6. Maximum Sum Two Non-Overlapping Subarrays
Kadane's algorithm can also be used to find the maximum sum of two non-overlapping subarrays of a given array. The two subarrays should not overlap and their lengths can be different.
To find the maximum sum of two non-overlapping subarrays, we can use Kadane's algorithm twice. First, we use Kadane's algorithm to find the maximum sum subarray from the beginning of the array to each element. We store the maximum sum subarray in an array `prefix_max`. Second, we use Kadane's algorithm to find the maximum sum subarray from the end of the array to each element. We store the maximum sum subarray in an array `suffix_max`. Finally, we iterate over the array and compute the maximum sum of two non-overlapping subarrays that end at the current element.
7. Maximum Sum of K Consecutive Elements
Kadane's algorithm can be used to find the maximum sum of `k` consecutive elements in an array. To do this, we first find the maximum sum subarray of length `k` using Kadane's algorithm. We then slide a window of size `k` over the array and compute the sum of each subarray of length `k`. The maximum of these sums is the maximum sum of `k` consecutive elements in the array.
8. Largest Sum Zigzag Subsequence
Kadane's algorithm can be used to find the largest sum zigzag subsequence of a given array. A zigzag subsequence is a sequence in which the elements alternate between increasing and decreasing. The largest sum zigzag subsequence is the zigzag subsequence with the largest sum.
To find the largest sum zigzag subsequence, we use Kadane's algorithm twice. First, we use Kadane's algorithm to find the maximum sum subsequence of the array that ends with an increasing element. We store the maximum sum subsequence in an array `increasing_max`. Second, we use Kadane's algorithm to find the maximum sum subsequence of the array that ends with a decreasing element. We store the maximum sum subsequence in an array `decreasing_max`. Finally, we iterate over the array and compute the maximum sum of zigzag subsequence that ends at the current element.
9. Maximum Sum Rectangle in a 2D Matrix
Kadane's algorithm can be used to find the maximum sum rectangle in a 2D matrix. The maximum sum rectangle is the rectangular submatrix with the largest sum.
To find the maximum sum rectangle, we first fix the left and right borders of the rectangle. We then use Kadane's algorithm to find the maximum sum subarray of each row between the left and right borders. We store the maximum sum subarray in an array `temp`. We then compute the maximum sum subarray of `temp` using Kadane's algorithm. The maximum of all such maximum sum subarrays is the maximum sum rectangle in the matrix.
10. Maximum Sum Triplet in an Array
Kadane's algorithm can be used to find the maximum sum triplet in an array. The maximum sum triplet is the triplet of elements with the largest sum.
To find the maximum sum triplet, we first fix the middle element of the triplet. We then use Kadane's algorithm to find the maximum sum subarray of the array to the left of the middle element. We store the maximum sum subarray in an array `left_max`. Second, we use Kadane's algorithm to find the maximum sum subarray of the array to the right of the middle element. We store the maximum sum subarray in an array `right_max`. Finally, we iterate over the array and compute the maximum sum triplet that includes the current element.
Conclusion
Kadane's algorithm is a powerful tool for solving a variety of problems related to arrays. It is simple to understand and implement, and has a linear time complexity. In this blog post, we explored how Kadane's algorithm works and listed some of the problems that can be solved using it. I hope you found this blog post helpful and informative!