Maximum Subarray Sum

Solution of the problem and discussion of Kadane’s algorithm

Dec 18, 20173 min read

Overview:

Maximum Subarray Sum is a popular programming problem. In this article, we will try to dissect the problem and try to solve it with a popular algorithm called the Kadane’s Algorithm which is very specific to the problem. I am going to use JavaScript to write my solution function but please feel free to apply the algorithm in any language you like.

Problem:

Find the sum of the contiguous subarray within an array which has the largest sum.

For example, given the following array:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

the contiguous subarray:

[4, 1, 2, 1]

has the largest sum:

6

If you want to try the problem first please go ahead try it on Codewars.

Solution:

I am going to write the entire solution first and discuss the application of the algorithm going through it:

const maxSubarray = arr => {  
  let max_ending_here = 0, max_so_far = 0  
  arr.forEach(n => {  
    max_ending_here = Math.max(n, max_ending_here + n)  
    max_so_far = Math.max(max_so_far, max_ending_here)  
  })  
  return max_so_far  
}

Go ahead and take a moment to understand each line of the solution.

Kadane’s Algorithm:

Kadane’s algorithm is a linear time algorithm developed by a professor at Carnegie Mellon University named Jay Kadane, hence the name of the algorithm.

This algorithm is based on splitting up possible solution subarrays and comparing their sum to find the subarray with the largest sum. Let’s discuss some of the important lines from the above code.

max_ending_here:

One fact we can be certain of is that each possible subarray will have each element from the original array as its last element. Meaning, the possible subarrays could be:

[-2]  
[-2, 1]  
[1]  
[-2, 1, -3]  
[1, -3]  
[-3]  
...

Where each subarray ends in either [-2], [1], [-3], … and so on to the last element of the array.

We can exploit this fact by going through each element of the array and finding the maximum sum of the subarray ending with that element, which we can store in the max_ending_here variable.

max_ending_here is basically the sum of all elements in that possible subarray. Therefore, we can add all the elements to max_ending_here as we go through the array.

max_ending_array += n

We can also take this opportunity to eliminate all the improbable subarrays by comparing the max_ending_array with the current element. If the current element is larger than the max_ending_array then our solution subarray would definitely not start with the elements before the current element. Meaning, we can now reset the max_ending_here to the larger value of the max_ending_here and the current element.

max_ending_here = Math.max(n, max_ending_here + n)

max_so_far:

We also need to keep track of the largest sum of all possible subarrays as we go through each of them. This value can be updated each time the max_ending_here is updated. This value should be the larger value between max_so_far and the current max_ending_here :

max_so_far = Math.max(max_so_far, max_ending_here)

As we finish iterating once over the array, we will have one maximum sum because we compared them in each iteration. Therefore, the remaining max_so_far should be our return value.

In a nutshell:

Maximum Subarray Sum is a popular problem and the brute force solution could be of quadratic or cubic time complexity. We can use the Kadane’s algorithm to solve the most basic version of this problem using the linear time complexity. We can also use this algorithm to solve more advanced versions of this problem.

Happy Problem Solving!