What is it?
Kadane’s algorithm is a highly optimized method to determine a contiguous subarray from an array such that it has the maximum sum, i.e. it is used to find a group of continuous elements of array whose sum is higher than the rest. On first look it seems like that would just be the entire array- however that is only the case if no negative elements exist in the array. When their presence exists, the problem becomes slightly more complicated and requires a specialized algorithm to handle the situation efficiently. Kadane's is a simple algorithm with a time complexity of O(n) and is an application of dynamic programming.
What is Dynamic Programming?
If a problem can be broken down into a collection of simpler subproblems, dynamic programming can be applied. The principle involves solving the subproblems just once and storing their solutions so that the previously computed solution can just be looked up, instead of it having to be recalculated every time, thus saving a lot of computation time and giving more efficient solutions.
How it works?
Kadane’s algorithm utilizes two variables- both initially set to 0. One is used to keep track of the sums of continuous elements in the array and another to keep track of the maximum sum so far. The code runs a loop through all the elements of the array once, adding the elements to variable 1. If ever the cumulative sum dips below 0, the variable is set to 0 again, because maximum sum will not then belong to that subarray. After every summation, the second variable is compared with the first- if the second variable is less than the first, and the value of this var2 is updated. This ensures that the second variable is holding the maximum value, and at the end, that’s our answer! Thus, the entire algorithm finds the max sum in just one pass through the array, instead of some other method like the simple brute force one. In that method, firstly all the possible subarrays of an array are found, and their elements summed- all these sums are then compared to find out the maximum. However, finding all subarrays means taking all possible lengths of array with A, then A and so on- which takes the complexity of the problem to O(n^2), thus rendering the solution to be very ineffective and costly, especially if n is big. Hence why we use Kadane’s algorithm.
Initializing max_till_now = 0
Initializing max_ending = 0
Repeat steps 4 to 6 for every element in the array
Set max_ending = max_ending + a[i]
if (max_ending<0) then set max_ending = 0
if (max_till_now < max_ending) then set max_till_now = max_ending
The above process is illustrated below using an example:
Why is it used?
The problem of finding maximum sum in subarray can be applied to various real life problems like analysis of a business’ profits to find out the time period with highest/ slowest growth, station travel in order( for optimal petrol utilization) as well Hotels along a coast (buying a continuous line of hotels such that maximum profit is earnt). Kadane’s algorithm is also widely used in image processing for finding the maximum likelihood estimation of patterns in digitized images.
Kadane’s algorithm is thus a widely used and efficient algorithm for finding maximum sum of contiguous subarray with a simple time complexity of O(n), with its straightforward approach making it an easy to understand problem in the foray into dynamic programming.