Kadane's Algorithm

Maximum Subarray Sum: Kadane's Algorithm

If you are competitive programming or preparing for campus placements or technical interviews, you might have probably come across something like this:
*Given an array arr[] of N integers. Find the contiguous sub-array which has the maximum sum and return its sum. *
If not, so does the "Kadane's Algorithm" rings any bell?
Kadane's algorithm is an iterative dynamic programming approach in which we search for a maximum sum contiguous subarray within a one-dimensional numeric array.

Working of Kadane's Algorithm
Some may think okay it's just the sum of all elements in an array. But an array may have negative integer elements, which decreases the total array's sum.
Thus we can say that the sum of all array elements isn't always the case.
A simple idea of Kadane's algorithm is to look for all positive contiguous segments of array and keep track of the maximum sum contiguous subarray among all positive segments.
An array is a contiguous memory block. So, a subarray is a slice of contiguous array that maintains the order of the elements.
Let us consider an array:
arr={1,2,3,4}
For this array, the sub-arrays are:
For elements at 0th index {1},{1,2},{1,2,3},{1,2,3,4}
For elements at 1st index {2},{2,3},{2,3,4}
For elements at 2nd index {3},{3,4}
For elements at 3rd index {4}
Now we know sub-arrays for an array.
Brute Force Approach
The brute force solution calculates the sum of each sub-array and then compares the results to determine the maximum sum of all sub-arrays sums. This method is straight forward, but it is not used commonly.
This is because it has a time complexity of O(N^3) and O(N) space complexity.
As we know, while writing any program, Time and Space Complexity plays a vital role in choosing the algorithm. Therefore, Kadane's algorithm is used because of its advantage considering time and space complexity.
Kadane's Algorithm

1. First, we will consider two elements, one which stores the maximum end of the subarray and another which stores the maximum sum far.
2. Let the two elements be named variables as max_end and max_far, respectively.
3. We will initialise both as 0.
4. Each time we get a positive sum, we compare it with max_end and update max_far if it is greater than it. The Time and Space complexity are as: Time Complexity: O(N) Space Complexity: O(1) Comparing the "Time and Space Complexity" of 'Brute Force Approach' and of 'Kadan's Algorithm', the latter is better when it comes to solving the same problem. Hence, Kadane's algorithm is preferred method when it comes to finding the maximum contiguous sub-array sum.

Special Case
For all the negative numbers in an array, all the elements in array are less than 0. So, we compare the sum of the consecutive elements with the current element from the array.