В чем изьяны моего чудища?

Question

[Сарван Джаваскриптович]

'use strict'
function getMaxSubSum(arr){
  let a = 0;
  let b = 0;
  let c = 0;
  for(let i of arr){
    a += i;
    if(b < a){
      c = a;
    }else if(b > a){
      a = 0;
    }
    b += i;
  }
  return c;
}
let arr = [1,2,3,5,-66,22,333,-2223,213,1122];
console.log(getMaxSubSum(arr));

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

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

Функция getMaxSubSum(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 (берём все)
Если все элементы отрицательные – ничего не берём(подмассив пустой) и сумма равна «0»:

getMaxSubSum([-1, -2, -3]) = 0
Попробуйте придумать быстрое решение: O(n2), а лучше за О(n) операций.
Хотелось бы посмотреть на ваше решение 0_0

Comments

[WbICHA]

В чем изьяны моего чудища?

К примеру, в этом:

if(b > a){
      a = 0;
    }

Что приводит к:

console.log(getMaxSubSum([11, -1, 2, 3, 9])); // 11 != 24

[be_a_man]

WbICHA,

[11, -1, 2, 3, 9]
// 11 + -1 + 2 + 3 + 9 = 24

[WbICHA]

be_a_man, к чему это?

Answer 1

[Сергей Соколов]

В вашем коде не сравниваются все возможные варианты.
Он проваливает два примера из вопроса:
[2, -1, 2, 3, -9] = 6 (у вас получается 5)
и [-2, -1, 1, 2] = 3 (у вас выводит 2)

spoiler

Предлагаю такой вариант решения. Возможно, не оптимальный. Полный перебор.

Будем двигать «окно» по массиву, считая сумму элементов в нём. Размер окна от всего массива до окошечка размером в 1 элемент.
Считаем сумму в начальном положении окна. Затем, двигаясь вправо, вычитаем элемент слева и прибавляем элемент справа.

Минимально возможная сумма — ноль.

function getMaxSubSum(arr) {
  let max = 0;
  const length = arr.length;

  for (let frame = length; frame > 0; frame--) {
    let sum = 0;
    for (let i = 0; i < frame; i++) sum += arr[i];
    max = Math.max(max, sum);

    // move frame
    for (let offset = 1; offset <= length - frame; offset++) {
      sum -= arr[offset - 1];
      sum += arr[offset + frame - 1];
      max = Math.max(max, sum);
    }
  }

  return max;
}


const tests = () => {
  [
    [[-1, 2, 3, -9], 5],
    [[2, -1, 2, 3, -9], 6],
    [[-1, 2, 3, -9, 11], 11],
    [[-2, -1, 1, 2], 3],
    [[100, -9, 2, -3, 5], 100],
    [[1, 2, 3], 6],
    [[-1, -2, -3], 0],
  ].forEach((el, i) => {
    const result = getMaxSubSum(el[0]);
    console.assert(result === el[1], "Test %d failed: [%s] %d != %d", i, el[0], result, el[1]);
  })
}

tests();

Comments

[WbICHA]

let window = length

Жестокий ты.)

[Сергей Соколов]

WbICHA, аааа! 8 ))) Че-т задумался об абстракциях.

Answer 2

[lugindev]

const getMaxSumm = arr => arr.reduce((acc, el) => {
    acc[1] += el, acc[0] = Math.max(...acc)
    acc[1] < 0 && (acc[1] = 0)
    return acc
}, [0, 0])[0]

function tests() {
    [
        [[2, -1, 2, 3, -9], 6],
        [[-1, 2, 3, -9], 5],
        [[2, -1, 2, 3, -9], 6],
        [[-9, 7, 2, 3, -9], 12],
        [[-1, 2, 3, -9, 11], 11],
        [[-2, -1, 1, 2], 3],
        [[100, -9, 2, -3, 5], 100],
        [[1, 2, 3], 6],
        [[1, 2, 3, 5, -66, 22, 333, -2223, 213, 1122], 1335]
    ].forEach(arr => {
        console.log(getMaxSumm(arr[0]), arr[1])
    })
}

tests()