Introduction:
Kadane's algorithm is a dynamic programming algorithm used to find the maximum sum subarray of a given array of integers.
It was discovered by Jay Kadane in 1984. The algorithm is widely used in various applications, such as data analysis, image processing, and computer vision.
The algorithm can be implemented in linear time and constant space complexity, making it a very efficient solution to the maximum sum subarray problem.
Problem Statement:
The maximum sum subarray problem can be stated as follows: given an array of integers, find a contiguous subarray with the largest sum.
For example, consider the following array of integers:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
The maximum sum subarray of this array is [4, -1, 2, 1], with a sum of 6.
Brute force Maximum Sum Subarray:
The brute force solution for Kadane's algorithm involves generating all possible subarrays of the given array and finding the subarray with the maximum sum. This solution has a time complexity of O(n^2), which is not efficient for larger arrays.
Here's the brute force solution in pseudocode:
for i = 0 to n-1
sum = 0
for j = i to n-1
sum = sum + a[j]
max_sum = max(max_sum, sum)
return max_sum
In this algorithm, `a` is the input array of integers, `n` is the length of the array, `max_sum` is the maximum sum found so far, `sum` is the sum of the current subarray being considered, and `max` is a function that returns the maximum of two integers.
The algorithm works as follows:
1. We initialize `max_sum` to the smallest possible integer value.
2. We iterate over all possible subarrays of the input array. For each
subarray, we compute the sum of its elements.
3. We update `max_sum` to be the maximum of `max_sum` and the sum of the
current subarray.
4. We return `max_sum` as the result.
While this solution is simple to understand, it is not efficient for larger arrays. For an array of length `n`, there are O(n^2) possible subarrays, so the time complexity of this solution is O(n^3). For large values of `n`, this solution can be very slow.
Kadane's algorithm, on the other hand, has a time complexity of O(n) and is much more efficient for larger arrays.
Kadane's Algorithm:
Kadane's algorithm is based on the observation that the maximum sum subarray ending at position i is either the element at position i itself, or the maximum sum subarray ending at position i-1 plus the element at position i.
To find the maximum sum subarray of the entire array, we can iterate over the array, and at each position i, we compute the maximum sum subarray ending at position i. We keep track of the maximum sum found so far, and return it as the result.
Algorithm in pseudocode:
Here's the algorithm in pseudocode:
sum = 0
for i = 0 to n-1
sum = sum + a[i]
max_sum = max(max_sum, sum)
if sum < 0
sum = 0
return max_sum
In this algorithm, a is the input array of integers, n is the length of the array, max_sum is the maximum sum found so far, and sum is the maximum sum subarray ending at position i.
Algorithm working:
The algorithm works as follows:
We initialize max_sum to the smallest possible integer value, and sum to 0.
We iterate over the array, and at each position i, we add the element at position i to sum.
We update max_sum to be the maximum of max_sum and sum. This ensures that max_sum always holds the maximum sum found so far.
If sum is negative, we reset it to 0. This ensures that any subsequent subarrays will not include the negative sum, because a subarray with a negative sum cannot be the maximum sum subarray.
We return max_sum as the result.
Example:
Let's walk through an example of using Kadane's algorithm to find the maximum sum subarray of the following array of integers:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
We initialize max_sum to INT_MIN (-2^31), and sum to 0.
We start iterating over the array. At the first position (i=0), we add -2 to
sum, giving us sum=-2.
We update max_sum to be the maximum of max_sum
and sum, which is -2. So max_sum is now -2.
We continue iterating over the array. At the second position (i=1), we add 1
to sum, giving us sum=-1.
We update max_sum to be the maximum of max_sum
and sum, which is 1. So max_sum is now 1.
We continue iterating over the array. At the third position (i=2), we add -3
to sum, giving us sum=-2.
We update max_sum to be the maximum of max_sum
and sum, which is 1. So max_sum remains 1.
We continue iterating over the array. At the fourth position (i=3), we add 4
to sum, giving us sum=2.
We update max_sum to be the maximum of max_sum
and sum, which is 4. So max_sum is now 4.
We continue iterating over the array. At the fifth position (i=4), we add -1
to sum, giving us sum=1.
We update max_sum to be the maximum of max_sum
and sum, which is 4. So max_sum remains 4.
We continue iterating over the array. At the sixth position (i=5), we add 2 to
sum, giving us sum=3.
We update max_sum to be the maximum of max_sum and
sum, which is 4. So max_sum remains 4.
We continue iterating over the array. At the seventh position (i=6), we add 1
to sum, giving us sum=4.
We update max_sum to be the maximum of max_sum
and sum, which is 4. So max_sum remains 4.
We continue iterating over the array. At the eighth position (i=7), we add -5 to sum, giving us sum=-1. Since sum is negative, we reset it to 0. We do not update max_sum, so max_sum remains 4.
We continue iterating over the array. At the ninth position (i=8), we add 4 to
sum, giving us sum=4.
We update max_sum to be the maximum of max_sum and
sum, which is 4. So max_sum remains 4.
We have finished iterating over the array. We return max_sum as the result, which is 4.
So the maximum sum subarray of the input array is [4, -1, 2, 1], with a sum of 6, which is the correct output.
Solution Code:
Hands-on solution code:
Leetcode solution code:
Conclusion:
Kadane's algorithm is a simple and elegant solution to the maximum sum subarray problem, with a time complexity of O(n) and a space complexity of O(1). The algorithm is widely used in various applications and is a good example of how dynamic programming can be used to solve a complex problems efficiently.
I hope this blog post has helped you understand Kadane's algorithm better. If you have any questions or comments, feel free to leave them below!