Как найти наибольшую последовательность элементов в массиве, чья сумма равна нулю?

Question

[campus1]

Есть задачка =>
Дан массив чисел, надо в этом массиве найти наибольшую последовательность чисел, которая = 0.
Например =>

maxZeroSequence([25, -35, 12, 6, 92, -115, 17, 2, 2, 2, -7, 2, -9, 16, 2, -11]);

Должно вернуть
[92, -115, 17, 2, 2, 2]

Мой код =>

function maxZeroSequenceLength(array) {
    let resultArr,
        numbers;

    for (let i = 0; i < array.length; i++) {
        numbers = 0;
        for (let j = i; j < array.length; j++) {
            numbers += array[j];
            if (numbers === 0) {
                resultArr = array.slice(i, j + 1);
            }
        }
    }
    return resultArr;
}

У меня возвращает
[2, -9, 16, 2, -11].
Подскажите где я туплю?
P.S Думаю надо еще добавить какую-то проверку на длительность массива (возможно).

Answer 1

[0xD34F]

Как минимум, проблема в том, что вы хватаете каждый попавшийся подмассив с нулевой суммой. Соответственно, успешно найденный максимальный подмассив будет затёрт меньшим, но расположенным ближе к концу массива. Надо запоминать индексы начала и конца подмассива и смотреть их разности, например:

function maxZeroSequence(arr) {
  let iMin = 0;
  let iMax = 0;

  for (let i = 0; i < arr.length; i++) {
    let sum = 0;

    for (let j = i; j < arr.length; j++) {
      if ((sum += arr[j]) === 0 && (iMax - iMin) <= (j - i + 1)) {
        iMin = i;
        iMax = j + 1;
      }
    }
  }

  return arr.slice(iMin, iMax);
}

Кроме того, проверка всех возможных подмассивов может оказаться слишком медленной при большом размере массива. Так что лучше посчитать префиксные суммы, попутно запоминая индексы, где та или иная сумма встретилась в первый и последний раз; ну а далее взять подмассив с максимальной разностью индексов:

function maxZeroSequence(arr) {
  const sumIndices = Object.values(arr.reduce((acc, n, i) => {
    const sum = acc[0] += n;
    (acc[1][sum] = acc[1][sum] || [ i + 1 ])[1] = i + 1;
    return acc;
  }, [ 0, { 0: [ 0 ] } ])[1]);

  return arr.slice(...sumIndices.reduce((max, n) => {
    const diff1 = n[1] - n[0];
    const diff2 = max[1] - max[0];
    return diff1 > diff2 || (diff1 === diff2 && n[0] > max[0]) ? n : max;
  }, [ 0, 0 ]));
}

Comments

[campus1]

Ага понял, спасибо. Щас себе разберу.