Наибольшая сумма подряд идущих элементов массива

Условие

Необходимо определить непрерывный подмассив в заданном массиве чисел, у которого сумма элементов достигает максимального значения, и вернуть эту сумму. Если все элементы массива отрицательные, следует вернуть 0.

Ответ

Используйте алгоритм Кадане с разрешённым пустым подмассивом: текущую сумму обнуляйте, если она стала отрицательной. Максимум начинайте с нуля.

function maxSubarraySum(numbers) {
  let current = 0, best = 0;
  for (const value of numbers) {
    current = Math.max(0, current + value);
    best = Math.max(best, current);
  }
  return best;
}

Для [-2,3,-1,4,-6] ответ 6: участок [3,-1,4]. Для всех отрицательных чисел и пустого массива результат 0, как требует условие. Нельзя просто сложить положительные элементы: подмассив должен быть непрерывным. Время O(n), дополнительная память O(1).