Sum Array Toy Problem

One of the toy problems I was given over the last couple weeks was called Sum Array — a problem where I was tasked with finding the greatest contiguous sum of numbers in that array.

The input for the function is an array of any length, containing positive or negative numbers — or a combination of both. The expected output is a single number, representing the largest possible sum for that array of numbers.

The provided examples are:

Input: [1, 2, 3]

Expected Output: 6

Input: [4, -1, 5]

Expected Output: 8

Input: [10, -11, 11]

Expected Output: 11

Input: [1, 2, 3, -6, 4, 5, 6]

Expected Output: 15

Given those examples, I immediately recognized one of the edge cases: a single array item can count as a contiguous sum — which is the case with [10, -11, 11] outputting 11.

In order to solve this problem I determined I needed two variables, initially set to zero:

var max = 0;
var current = 0;

Max represents the largest sum available in the array, which will be the return value for the function, and current which represents the sum that is currently being added to.

Next, I looped through the input array and determined if current plus the value at array[i] was smaller or larger than the single value at array[i]. If current + array[i] is smaller, current would be reassigned to array[i]. If not, current would be reassigned to the sum of current and array[i].

Then, still inside that loop, I would determine if that newly reassigned current is larger than the value at max at that time. If so, I reassign max to equal current.

for (var i = 0; i < array.length; i++) {
if (current + array[i] < array[i]) {
current = array[i];
} else {
current += array[i];
}
if (current > max) {
max = current;
}
}

At this point, I assumed I was finished with this toy problem and excitedly went to submit when I encountered an edge case I hadn’t expected — an array of all negative values. The way my current solution dealt with this situation was to return 0; which is what I set max as for default and was never reassigned because all the values in this array were less than that max.

Input: [-3, -2, -1, -2, -3]

Expected Output: -1

So, although certainly there are more elegant and succinct ways to handle this particular edge case, I determined the most straight-forward solution that would require the least refactoring of my original solution was to add a final if statement at the end — if after all the loops, max still equals 0, find the largest number in the array and assign that as max.

I did this using the Math.max function which returns the largest of a collection of numbers. To pass the entire array at once, I used the spread operator (…) — which essentially performs the same function as Function.prototype.apply in cases where you want to use an array as arguments to a function.

if (max === 0) {
max = Math.max(... array);
}

So my final solution for Sum Array is:

function sumArray (array) {
var max = 0;
var current = 0;
for (var i = 0; i < array.length; i++) {
if (current + array[i] < array[i]) {
current = array[i];
} else {
current += array[i];
}
if (current > max) {
max = current;
}
}
if (max === 0) {
max = Math.max(... array);
}
return max;
}
Like what you read? Give Grace Halbert a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.