Kadane's Algorithm
Kadane’s
algorithm is used to find largest contagious subarray sum for a given array. It
is one of the most common types of algorithms used to find the subarray with largest
sum. The time complexity of this algorithm is O(N).
Output:
Code Explanation:
On line 4, there’s an int array variable a[ ], which is the array on which we have to perform our task. We have stored the value of the array, in variable l.
cur_max, is a temporary variable for traversing the array and storing positive sum occurring and update it after each iteration. global_max, is a variable for storing the highest sum of subarray. ‘start’ variable stores the starting index of the desired subarray and ‘end’ variable stores the last index of that subarray, that is, contagious subarray with the highest sum.
Working:
Talking about the working of this algorithm, it uses one for loop and the entire operation can be performed in just one traversal of the array. One of the limitations of this algorithm is that it needs at least one positive number in the array otherwise it will not work.
Algorithm:
1. Start
2. Declare an array with at least one
positive number.
3. Declare two counter variables, first,
cur_max for current sum and the other global_max for global sum. The variable
global_max will be initialized with minimum integer value. The variable global_max
will store largest sum of the required subarray.
4. Declare a for loop starting from the
first index and terminating at the last index. Inside the for loop,
cur_max
+= a[i]
if(cur_max>global_max)
{
global_max=cur_max
}
if (cur_max<0)
{
cur_max=0
}
End of for
loop
Variable cur_max
is used to add the elements of the array at each iteration and compare it with
the value of global_max at each iteration. If the value of global_max is less
than cur_max then assign it with the value of cur_max. If the value of cur_max
is less than 0 then assign cur_max with the value 0.
5. The value stored in the global_max variable is the output of our program.