Maximum subarray
JavaScript, Algorithm, Math, Array · Sep 7, 2022

Finds a contiguous subarray with the largest sum within an array of numbers.
- Use a greedy approach to keep track of the current
sum
and the current maximum,maxSum
. SetmaxSum
to-Infinity
to make sure that the highest negative value is returned, if all values are negative. - Define variables to keep track of the maximum start index,
sMax
, maximum end index,eMax
and current start index,s
. - Use
Array.prototype.forEach()
to iterate over the values and add the current value to thesum
. - If the current
sum
is greater thanmaxSum
, update the index values and themaxSum
. - If the
sum
is below0
, reset it to0
and update the value ofs
to the next index. - Use
Array.prototype.slice()
to return the subarray indicated by the index variables.
const maxSubarray = (...arr) => {
let maxSum = -Infinity,
sum = 0;
let sMax = 0,
eMax = arr.length - 1,
s = 0;
arr.forEach((n, i) => {
sum += n;
if (maxSum < sum) {
maxSum = sum;
sMax = s;
eMax = i;
}
if (sum < 0) {
sum = 0;
s = i + 1;
}
});
return arr.slice(sMax, eMax + 1);
};
maxSubarray(-2, 1, -3, 4, -1, 2, 1, -5, 4); // [4, -1, 2, 1]
Written by Angelos Chalaris
I'm Angelos Chalaris, a JavaScript software engineer, based in Athens, Greece. The best snippets from my coding adventures are published here to help others learn to code.
If you want to keep in touch, follow me on GitHub.