Вернуться к уроку

Подмассив наибольшей суммы

важность: 2

На входе массив чисел, например: arr = [1, -2, 3, 4, -9, 6].

Задача – найти непрерывный подмассив arr, сумма элементов которого максимальна.

Ваша функция должна возвращать только эту сумму.

Например:

getMaxSubSum([-1, 2, 3, -9]) = 5 (сумма выделенных)
getMaxSubSum([2, -1, 2, 3, -9]) = 6
getMaxSubSum([-1, 2, 3, -9, 11]) = 11
getMaxSubSum([-2, -1, 1, 2]) = 3
getMaxSubSum([100, -9, 2, -3, 5]) = 100
getMaxSubSum([1, 2, 3]) = 6 (неотрицательные - берем всех)

Если все элементы отрицательные, то не берём ни одного элемента и считаем сумму равной нулю:

getMaxSubSum([-1, -2, -3]) = 0

Постарайтесь придумать решение, которое работает за O(n2), а лучше за O(n) операций.

Открыть песочницу с тестами для задачи.

Подсказка (медленное решение)

Можно просто посчитать для каждого элемента массива все суммы, которые с него начинаются.

Например, для [-1, 2, 3, -9, 11]:

// Начиная с -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// Начиная с 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// Начиная с 3:
3
3 + (-9)
3 + (-9) + 11

// Начиная с -9
-9
-9 + 11

// Начиная с 11
11

Сделайте вложенный цикл, который на внешнем уровне бегает по элементам массива, а на внутреннем – формирует все суммы элементов, которые начинаются с текущей позиции.

Медленное решение

Решение через вложенный цикл:

function getMaxSubSum(arr) {
  var maxSum = 0; // если совсем не брать элементов, то сумма 0

  for (var i = 0; i < arr.length; i++) {
    var sumFixedStart = 0;
    for (var j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

Такое решение имеет оценку сложности O(n2), то есть при увеличении массива в 2 раза алгоритм требует в 4 раза больше времени. На больших массивах (1000, 10000 и более элементов) такие алгоритмы могут приводить к серьёзным «тормозам».

Подсказка (быстрое решение)

Будем идти по массиву и накапливать в некоторой переменной s текущую частичную сумму. Если в какой-то момент s окажется отрицательной, то мы просто присвоим s=0. Утверждается, что максимум из всех значений переменной s, случившихся за время работы, и будет ответом на задачу.

Докажем этот алгоритм.

В самом деле, рассмотрим первый момент времени, когда сумма s стала отрицательной. Это означает, что, стартовав с нулевой частичной суммы, мы в итоге пришли к отрицательной частичной сумме – значит, и весь этот префикс массива, равно как и любой его суффикс имеют отрицательную сумму.

Следовательно, от всего этого префикса массива в дальнейшем не может быть никакой пользы: он может дать только отрицательную прибавку к ответу.

Быстрое решение

function getMaxSubSum(arr) {
  var maxSum = 0,
    partialSum = 0;
  for (var i = 0; i < arr.length; i++) {
    partialSum += arr[i];
    maxSum = Math.max(maxSum, partialSum);
    if (partialSum < 0) partialSum = 0;
  }
  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0

Информацию об алгоритме вы также можете прочитать здесь: http://e-maxx.ru/algo/maximum_average_segment и здесь: Maximum subarray problem.

Этот алгоритм требует ровно одного прохода по массиву, его сложность имеет оценку O(n).

Открыть решение с тестами в песочнице.