Как найти максимальную сумму, которую можно получить сложением произвольной неразрывной последовательности элементов массива?

Question

[_ _]

Задачка была следующая - дан массив длинной до 200, 000 элементов, элементами которого являются целые числа в диапазоне [-10000, 10000].
Нужно найти максимальную сумму, которую можно получить сложением произвольной неразрывной последовательности элементов этого массива.
Типа для входных данных [2,-2,-5,2,2,-1,2,-3] будет 5 - сумма подмассива [2,2,-1,2]

Я в алгоритмах не силен, но вроде как нащупал верный, правда забыл про смешное граничное условие и не успел закончить вовремя.

Как бы вы стали решать эту задачу?
В условии также есть ограничение по времени выполнения алгоритма - не более 2-х секунд в их интерпретаторе.

Answer 1

[demolishka]

Задача решается за линейное время. Будем поддерживать текущую сумму sum некоторой части массива. Ответ храним в переменной ans. Теперь сам алгоритм.
1. Проходим по массиву и обновляем текущую сумму sum.
2. Если в какой-то момент сумма sum стала отрицательной, то обнуляем ее: sum = 0.
3. В каждый момент времени обновляем ответ ans = max{ ans, sum }.

Можно доказать, что приведенный алгоритм корректно решает задачу.

Comments

[brevis]

А если все элементы отрицательные?

[Rsa97]

@brevis Тогда максимальной будет сумма пустой подпоследовательности массива.

[brevis]

Но ведь при [-5, -5, -1, -1, -1, -5, -5] max=-3 ? Или я что-то путаю?

[Rsa97]

sum([]) = 0, 0 > -3

[Rsa97]

@brevis А если запретить пустую подпоследовательность, то для вашего случая будет sum([-1]) = -1, что тоже больше -3. Для всего массива максимальной суммой при наличии только отрицательных чисел тогда будет максимальное из этих чисел.

[brevis]

@Rsa97 да-да, точно, -1. Все оказалось намного проще, чем я себе начал представлять. Спасибо.

[Rsa97]

Кстати, алгоритм при этом почти не меняется. Достаточно в том же цикле найти максимальный элемент массива (maxVal), и в конце алгоритма, если maxVal < 0, то ans = maxVal.

Answer 2

[Rsa97]

int sum = 0;
int maxSum = 0;
for (int i = 0; i < len; i++) {
    sum += val[i];
    if (sum > maxSum)
        maxSum = sum;
    if (sum < 0)
        sum = 0;
}

Answer 3

[_ _]

Да, совсем я стар стал - такой элементарный алгоритм прохлопал :)

Answer 4

[Станислав Ломадуров]

Решение в лоб

var a = [], // Array
    i = 0, x,
    current = a[0] + a[1],
    max = current;

for (i = 0; i in a; i++) {
    current = a[i];
    for (x = i + 1; x in a; x++) {
        current = current + a[x];
        if (current > max) {
            max = current;
        }
    }
}
console.log('Result:', max);

Comments

[_ _]

Тут уже сложность нелинейная, на большом массиве такое в две секунды не влезет

[Станислав Ломадуров]

Сложность нелинейная, поэтому и в лоб ))
Вот рабочий пример с замерами repl.it/N9K/1

[Rsa97]

Только алгоритм ошибочный. На примере из вопроса выдаёт не 5, а 4. Ошибка в том, что уменьшение current (current + a[x] < current) не означает, что подпоследовательность закончилась.

[Станислав Ломадуров]

@Rsa97 в тесте уже исправленная версия.

[Rsa97]

@lomatek Только она всё равно на массиве [2,-2,-5,2,2,-1,2,-3] выдаёт 4, а не 5.

[Станислав Ломадуров]

@Rsa97 опечатка в тексте исправленная. А тут не пройденное испытание (len 2000).

[Rsa97]

@lomatek Ещё одна ошибка - начальное присвоение значения current. Попробуйте на массиве [5,-1] или [-1].

[Rsa97]

@lomatek Да и в дальнейшей логике не учитывается, что нужная подпоследовательность может состоять из одного числа, например [-1,5,-1].

[Станислав Ломадуров]

@Rsa97 исхожу из условий, необходимо найти сумму. Единственная возможная сумма в массиве [5,-1] является 4.

[Rsa97]

@lomatek Но ведь не сказано, что массив не может быть пустым или состоять из одного элемента. Да и сумма вполне определена для одноэлементных (sum([x]) = x) и пустых (sum([]) = 0) множеств.

[Станислав Ломадуров]

@Rsa97 да, но только эту сумму нужно получить сложением элементов.

[Rsa97]

@lomatek В общем, чтобы понять, что имелось в виду в задании надо иметь тестовые примеры с контрольными результатами от авторов задания.