Нахождение макс суммы в ряде

AlexanderS · Вс янв 13, 2002 10:54 am

Задача:
Given a finite sequence of integers (they can be negative, zero, or positive), find the contiguous sub-sequence that yields the maximal sum of its elements.

For example, given the sequence [-1, 2, 3], the function would return [2, 3] out of possible [-1, 2, 3], [-1, 2], and [2, 3].

Она уже обсуждалась на Привете и было упомянуто, что она может быть решена с помощью интеграла. Но конкретного алгоритма небыло дано.

Интересует решение с наилучшим показателем O().

Alexander

sttranik · Вс янв 13, 2002 11:21 am

вроде простая задача - алгоритм "решения в лоб" довольно очевиден.

из исходного массива длиной N строим массив длиной M (M<=N). M - число положительных/отрицательных непрерывных последовательностей в исходном массиве (насчет нуля сами придумайте отнести его к положительному или отрицательному отрезку), каждый элемент массива M - сумма каждой такой последовательности. в дополнительном массиве можно сохранить индексы, определяющие каждую последовательность (типа 0, 4, 7, что соответствует 0-3, 4-6, 7-(N-1)). индексы нужны будут потом для ответа. теперь ищем максимум для значений (i,j) i,j=0..M-1, где каждое значение - сумма элементов в массиве M между i и j.

если в исходном массиве N преобладают длинные последовательности положительных/отрицательных чисел, то построение дополнительного массива M сильно облегчает жизнь, если знак чисел часто прыгает туда сюда, то нет. худший случай M=N.

наверное можно придумать какой то более умный алгорит поиска максимума сумм в массиве M, чем простой линейный поиск.

надо подумать на досуге [img:4573496e56]images/smiles/icon_smile.gif[/img:4573496e56]

Melkor · Вс янв 13, 2002 1:04 pm

<blockquote>quote:<hr>Originally posted by strannik
из исходного массива длиной N строим массив длиной M (M<=N). M - число положительных/отрицательных непрерывных последовательностей в исходном массиве (насчет нуля сами придумайте отнести его к положительному или отрицательному отрезку), каждый элемент массива M - сумма каждой такой последовательности. в дополнительном массиве можно сохранить индексы, определяющие каждую последовательность (типа 0, 4, 7, что соответствует 0-3, 4-6, 7-(N-1)). индексы нужны будут потом для ответа. <hr></blockquote>

Ну, это-то само собой. Кроме того, можно обрезать начальные и конечные отрицательные подмассивы (если есть). Получим последовательность +.-+.-+...-+. Обозначим si - текущий кандидат (включат начало, конец и сумму), smax - лучший кандидат из обработанных. Далее в цикле (заметим, что на каждой итерации a[i]<0 и a[i+1]>0):

<blockquote>code:<hr><pre>
for(i=1,si=smax={[0,0],a[0]};i<M;i+=2) {
smax = max(si,smax);
if (si > |a[i]|) // si-|a[i]|+|a[i+1]| > a[i+1]
si.end = i+1;
else
si.start = si.end = i+1;
}
smax = max(si,smax);
</pre><hr></blockquote>

Решение с интегралом, кстати, мне кажется неверным.

[ 13-01-2002: Message edited by: Melkor ]

Drom · Сообщение **Drom** » Вс янв 13, 2002 2:27 pm

<blockquote>quote:<hr>Originally posted by AlexanderS:
...
Интересует решение с наилучшим показателем O().
Alexander<hr></blockquote>

сложность будет O(N):
- один раз прочитать все значения придется => не меньше O(N),
- у меня получилось 3 прохода по массиву взад-вперед и 2 вспомогательныx массивa: значений последовательностей и индексов.

D.

[img:9978a06f0b]images/smiles/icon_sad.gif[/img:9978a06f0b] нифига не понял, что Melkor хотел своим кодом сказать

Drom · Сообщение **Drom** » Вс янв 13, 2002 4:11 pm

<blockquote>quote:<hr>Originally posted by Melkor:

...Что я хотел сказать - мы обрабатываем массив парами отрицательный-положительный элемент (подмассив). Имеем текущую сумму. Если, добавив к ней положительный элемент и вычев отрицательный, мы получаем большее значение, чем просто начав заново с положительного элемента, то мы так и делаем (иначе начинаем заново с положительного элемента). В любом случае на каждом шаге перед обновлением текущей суммы проверяем, не больше ли она, чем "лучшая".
<hr></blockquote>

спасибо, дошло. кажется это работает. осталось доказать почему [img:7a0ba12f6e]images/smiles/icon_wink.gif[/img:7a0ba12f6e]

Melkor · Вс янв 13, 2002 4:31 pm

<blockquote>quote:<hr>Originally posted by Drom:

спасибо, дошло. кажется это работает. осталось доказать почему [img:b8d7e04453]images/smiles/icon_wink.gif[/img:b8d7e04453] <hr></blockquote>

Ну, доказательство простое - а почему бы и нет, собственно? [img:b8d7e04453]images/smiles/icon_smile.gif[/img:b8d7e04453] Т.е., вроде, нет места, где бы мы могли что-то упустить: начало мы не должны прозевать, т.к. выбираем все время оптимальный вариант (продолжить текущую сумму или начать заново), а конец - т.к. мы регулярно сравниваем текущую сумму с лучшей.

coder · Вс янв 13, 2002 4:35 pm

<blockquote>quote:<hr>Originally posted by Drom:


спасибо, дошло. кажется это работает. осталось доказать почему [img:7c4c98ba71]images/smiles/icon_wink.gif[/img:7c4c98ba71] <hr></blockquote>

Ой, и до меня тоже дошло [img:7c4c98ba71]images/smiles/icon_biggrin.gif[/img:7c4c98ba71]

Тогда получаем 1 проход и 3 переменных. (одна - для суммы, а 2 других - чтобы не забыть, что в ответе написать "с .. по ..")

Попробую доказать более развернуто:
1. Последовательность должна начинаться с положительного (можно нули не в счет для простоты?) элемента и заканчиваться положительным элементом. Иначе, убрав первый или последний, получим бОльшую последовательность.
2. если у последовательности 1..n сумма отрицательная и начинается она с положительного элемента, а оканчивается отрицательным, и все ее возможные подпоследовательности, начинающиеся с положительного элемента и заканчивающиеся элементом n, тоже имеют отрицательную сумму, то последовательность n+1...m не может быть улучшена добавлением в ее начало одного или нескольких элементов из общей последовательности.

3. Решение, предложенное Melkor, удовлетворяет правилам 1 и 2.

clinger · Пн янв 14, 2002 12:12 am

<blockquote>quote:<hr>Originally posted by Дима:


Ой, и до меня тоже дошло [img:c1ed901a4a]images/smiles/icon_biggrin.gif[/img:c1ed901a4a]

Тогда получаем 1 проход и 3 переменных. (одна - для суммы, а 2 других - чтобы не забыть, что в ответе написать "с .. по ..")

Попробую доказать более развернуто:
1. Последовательность должна начинаться с положительного (можно нули не в счет для простоты?) элемента и заканчиваться положительным элементом. Иначе, убрав первый или последний, получим бОльшую последовательность.
2. если у последовательности 1..n сумма отрицательная и начинается она с положительного элемента, а оканчивается отрицательным, и все ее возможные подпоследовательности, начинающиеся с положительного элемента и заканчивающиеся элементом n, тоже имеют отрицательную сумму, то последовательность n+1...m не может быть улучшена добавлением в ее начало одного или нескольких элементов из общей последовательности.

3. Решение, предложенное Melkor, удовлетворяет правилам 1 и 2.<hr></blockquote>

Что-то с тремя переменными не получается. Может кто опишет процедуру для

[5, -1, 6]

И для

[-1, -2, -3]

.pl

clinger · Пн янв 14, 2002 12:16 am

<blockquote>quote:<hr>Originally posted by Melkor:
Ну, это-то само собой. Кроме того, можно обрезать начальные и конечные отрицательные подмассивы (если есть). Получим последовательность +.-+.-+...-+. Обозначим si - текущий кандидат (включат начало, конец и сумму), smax - лучший кандидат из обработанных. Далее в цикле (заметим, что на каждой итерации a[i]<0 и a[i+1]>0):
<hr></blockquote>

Это почему? Нигде не сказано, что положительные числа чередуются с отрицательными в последовательности. И обрезать подмассивы тоже нельзя, поскольку положительных чисел может вообще не быть.

.pl

Melkor · Пн янв 14, 2002 3:14 am

<blockquote>quote:<hr>Originally posted by Drom:
 [img:1540c03d0b]images/smiles/icon_sad.gif[/img:1540c03d0b] нифига не понял, что Melkor хотел своим кодом сказать<hr></blockquote>

Ну как, идем вдоль массива, накапливаем "текущую оптимальную" сумму (на каждой паре отрицательный-положительный подмассив можно принять однозначное решение, включать ее в эту сумму, или начинать с положительного подмассива). Периодически обновляем "лучшую" сумму по "текущей оптимальной". Подозрительно просто, но должно работать.

coder · Пн янв 14, 2002 3:24 am

Вот так попробуем:

имеем 2 переменных:
S - сумма всех элементов, начиная с первого и до текущего
k - индекс "максимального" элемента, т.е. того, на котором эта сумма имела максимум.

В результате первого прохода в k имеем индекс элемента, завершающего искомую последовательность

При втором проходе в k запоминаем наоборот тот элемент, на котором сумма была минимальной (не забывая, что на первом элементе S=0). Это первый элемент искомой последовательности.

Доказательство надо?

=====================
Продолжение:
мы получили <=2 проходов, используя 2 переменных.

Вопрос: Как обойтись одним проходом, имея 4 переменных?

coder · Пн янв 14, 2002 3:31 am

Прошу прощения, если я изложил частный случай чьего-то решения из предыдущих постов ибо Ваше решение, Melkor, (присоединяюсь к Drom) я тоже не понял, даже после пояснения. [img:89d99c7e01]images/smiles/icon_eek.gif[/img:89d99c7e01]

Melkor · Пн янв 14, 2002 3:35 am

<blockquote>quote:<hr>Originally posted by Дима:

имеем 2 переменных:
S - сумма всех элементов, начиная с первого и до текущего
k - индекс "максимального" элемента, т.е. того, на котором эта сумма имела максимум.

В результате первого прохода в k имеем индекс элемента, завершающего искомую последовательность

При втором проходе в k запоминаем наоборот тот элемент, на котором сумма была минимальной (не забывая, что на первом элементе S=0). Это первый элемент искомой последовательности.

Доказательство надо?

На [1, -100, 2] сработает? На первом проходе, как я понял, у Вас сумма будет [1, -99, -97], т.е. индекс 2 мы уже никак не получим.

мы получили <=2 проходов, используя 2 переменных.

Вопрос: Как обойтись одним проходом, имея 4 переменных?

Так а чем мое решение не подходит?

<hr></blockquote>

coder · Пн янв 14, 2002 3:43 am

Вы правы. чушь спорол-с [img:1516dfad69]images/smiles/icon_sad.gif[/img:1516dfad69]

Melkor · Пн янв 14, 2002 3:50 am

<blockquote>quote:<hr>Originally posted by Дима:
Прошу прощения, если я изложил частный случай чьего-то решения из предыдущих постов ибо Ваше решение, Melkor, (присоединяюсь к Drom) я тоже не понял, даже после пояснения. [img:1af47950f6]images/smiles/icon_eek.gif[/img:1af47950f6] <hr></blockquote>

Плохо у меня получается объяснять... Я всегда стараюсь сделать это как можно более компактно, но это обычно отрицаельно сказывается на качестве [img:1af47950f6]images/smiles/icon_sad.gif[/img:1af47950f6]

Что я хотел сказать - мы обрабатываем массив парами отрицательный-положительный элемент (подмассив). Имеем текущую сумму. Если, добавив к ней положительный элемент и вычев отрицательный, мы получаем большее значение, чем просто начав заново с положительного элемента, то мы так и делаем (иначе начинаем заново с положительного элемента). В любом случае на каждом шаге перед обновлением текущей суммы проверяем, не больше ли она, чем "лучшая".

Задачу эту, кстати, я решал раньше, когда читал старые приветовские топики.