Maximum subarray
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]