Coding Interview Question Kadane’s Algorithm

Kadane’s Algorithm 

Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.

Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.

Read About Coded transmission question.

Coded transmissions Coding Interview Question

Example 1:

Input:
N = 5
Arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which 
is a contiguous subarray.

Example 2:

Input:
N = 4
Arr[] = {-1,-2,-3,-4}
Output:
-1
Explanation:
Max subarray sum is -1 
of element (-1)

Your Task is to write the function maxSubarraySum() which takes Arr[] and N as input parameters and returns the sum of subarray with maximum sum.


Expected Time Complexity: O(N)
Expected Space Complexity: O(1)

Kadane’s Algorithm

To better understand Kadane’s Algorithm, first, we would go through a short introduction of Dynamic Programming and brute force approach. Then we would try to improve our approach and come up with a better algorithm, aka, Kadane’s Algorithm.

Maximum Subarray Problem

The maximum subarray problem is the task of finding the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers.

For example, for the array given above, the contiguous subarray with the largest sum is [4, -1, 2, 1], with sum 6. We would use this array as our example for the rest of this article. Also, we would assume this array to be zero-indexed, i.e. -2 would be called as the ‘0th’ element of the array and so on. Also, A[i] would represent the value at index i.

Now, we would have a look at a very obvious solution to the given problem.

Brute Force Approach

One very obvious but not so good solution is to calculate the sum of every possible subarray and the maximum of those would be the solution. We can start from index 0 and calculate the sum of every possible subarray starting with the element A[0], as shown in the figure below. Then, we would calculate the sum of every possible subarray starting with A[1], A[2] and so on up to A[n-1], where n denotes the size of the array (n = 9 in our case). Note that every single element is a subarray itself.

We will call the maximum sum of subarrays starting with element A[i] the local_maximum at index i. Thus after going through all the indices, we would be left with local_maximum for all the indices. Finally, we can find the maximum of these local_maximums and we would get the final solution, i.e. the maximum sum possible. We would call this the global_maximum.

But you might notice that this is not a very good method because as the size of array increases, the number of possible subarrays increases rapidly, thus increasing computational complexity. Or to be more precise, if the size of the array is n, then the time complexity of this solution is O(n²) which is not very good.

How can we improve this? Is there any way to use the concept of dynamic programming? Let’s find out.

Kadane’s Algorithm

In this section, we would use the brute force approach discussed above again, but this time we would start backward. How would that help? Let’s see.

We would start from the last element and calculate the sum of every possible subarray ending with the element A[n-1], as shown in the figure below. Then, we would calculate the sum of every possible subarray ending with A[n-2], A[n-3] and so on up to A[0].

Now let’s focus on the subarrays ending with the element A[4] (=-1) and A[5] (=2) shown in the figure below.

From the figure above, we see that the local_maximum[4] is equal to 3 which is the sum of the subarray [4, -1]. Now have a look at the subarrays ending with A[5]. You’ll notice that these subarrays can be divided into two parts, the subarrays ending with A[4] (highlighted with yellow) and the single element subarray A[5] (in green).

Let’s say somehow I know the local_maximum[4]. Then we see that to calculate the local_maximum[5], we don’t need to compute the sum of all subarrays ending with A[5] since we already know the result from arrays ending with A[4]. Note that if array [4, -1] had the maximum sum, then we only need to check the arrays highlighted with the red arrows to calculate local_maximum[5]. And this leads us to the principle on which Kadane’s Algorithm works.

local_maximun[i] = max(A[i], A[i] + local_maximun[i-1])

This way, at every index i, the problem boils down to finding the maximum of just two numbers, A[i] and (A[i] + local_maximum[i-1]). Thus the maximum subarray problem can be solved by solving these sub-problems of finding local_maximums recursively. Also, note that local_maximum[0] would be A[0] itself.

Using the above method, we need to iterate through the array just once, which is a lot better than our previous brute force approach. Or to be more precise, the time complexity of Kadane’s Algorithm is O(n).

Finally, let’s see how this all would work in code.

const maximumSubArray = (arr) => {
  let max_cur=arr[0], max_global = arr[0];
  for (let i = 1; i < arr.length; i++) {
    max_cur = Math.max(arr[i], max_cur + arr[i]);
    max_global = Math.max(max_cur, max_global);
  }  
  return max_global;
};
console.log(maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maximumSubArray([-10, -11, -12]));