Finding the Maximum Sub-Array Sum
As Christmas break is now here, I am still solving algorithms to give myself better practice. One problem I found is finding a maximum sum of a subset of an array. The question is, given an array with n elements, find the maximum sum of smaller arrays; more specifically, given an array
let array = [−2, 1, −3, 4, −1, 2, 1, −5, 4],find the maximum sum of subarrays of this array. The answer to this is the subarray
[4, −1, 2, 1]with a sum of 6. In this question, we want a continuous array; not adding the second number, the fifth, the tenth, the nth together.
So how do we start this problem? We will use Kadane’s algorithm. First we start off with a sum and max both at zero. Next thing we want to do is find the maximum between 0 and the sum added to the current array element and set the sum equal to this maximum. We do the same with max by finding the maximum between the max and the sum from the previous. We will iterate this with our array. The code is
sum = Math.max((array[x] + sum), 0)
max = Math.max(sum, max). The questions why do we need both, why not just use the first or second one. For sum, it is merely adding all the numbers from the first element to the jth element, and the new larger sum will replace the old sum. We are assuming 0 < j < n. For max, if the sum is larger than the max, the new max will be the sum and vice versa.
Now let’s make a chart to see what I mean.
I will explain how it goes. For convenience, I shall put the array here.
array = [−2, 1, −3, 4, −1, 2, 1, −5, 4]First element is -2. We set sum to be 0, so sum = Math.max(0–2, 0) = Math.max(-2, 0) = 0, and max = Math.max(0, -2) = 0. For the second element, the number is 1, so sum = Math.max(0+1,0) =1 ; max = Math.max(1,0) = 1. For the third, we have sum = Math.max(1–3,0) = 0, and max stays at 1. Keep iterating through this, and we will get the answer 6. This is Kadane’s algorithm. The full code is
let array = [1, -1, 5, 3, -7, 4, 5, 6, -100, 4] function largestSubarraySum(array){
// code to write here
var sum = 0
var max = 0
for(var x = 0; x < array.length; x++){
sum = Math.max((array[x] + sum), 0)
max = Math.max(sum, max)
}
return max
} largestSubarraySum(array).
It took me a while to understand this algorithm, and reading an article someone wrote and its Wikipedia article helped.
References
