AMar4enko
@AMar4enko

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

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

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

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

Можно доказать, что приведенный алгоритм корректно решает задачу.
Ответ написан
Rsa97
@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;
}
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
AMar4enko
@AMar4enko Автор вопроса
Да, совсем я стар стал - такой элементарный алгоритм прохлопал :)
Ответ написан
Комментировать
Решение в лоб
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);
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы