|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Polubasoff 2:5020/400 04 Mar 2002 09:53:03
To : Sergey Politov
Subject : поиск подмассива с максимальной суммой элементов
--------------------------------------------------------------------------------
Привет, Сергей!
В воскресенье, 03.03.2002 03:16, Sergey Politov писал к Ilya Sergeev:
IS>> Есть одномерный массив чисел. Hадо найти последовательность
IS>> (начальный и конечный индексы) элементов дающих максимальную сумму
IS>> элементов среди всех других последовательностей.
SP> Просто перебираешь начало и конец этой последовательности, и ищешь
SP> среди них с максимальной суммой. Если саму сумму считать по умному то
SP> решение будет за O(n^2), по умному это так (я не утверждаю что это
SP> наилучший способ, просто он сокращает время работы с O(n^3) до
SP> O(n^2)):
Грубовато. Hадо использовать динамическое программирование, тогда
решение находится за O(n).
Пусть А - данная последовательность. Представим её как совокупность
четырёх последовательностей
A = BMPE,
где Е - завершающая цепочка отрицательных и нулевых элементов,
где Р - предшествующая ей цепочка положительных и нулевых элементов,
где М - предшествующая ей цепочка отрицательных и нулевых элементов.
В, М и Е могут быть пусты.
Обозначим Sp = SUM(P), Sm = SUM(M),
S(X) - решение для подпоследовательности X.
Тогда S(A) = max (S(B), S(BMP), S(P)) = max (S(B), S(B)+Sm+Sp, Sp).
Отсюда сама возникает программа
for( --n; n >= 0 && a[n] <= 0; --n) {} // отбросить E
S = Sp = 0;
while (n >= 0) // пока последовательность не пуста
{
for( ; n >= 0 && a[n] >= 0; --n)
Sp += a[n]; // выделить Р, подсчитать Sp
if (Sp > S) S = Sp; // запомнить максимум среди S(P)
for( ; n >= 0 && a[n] <= 0; --n)
Sp += a[n]; // выделить М, подсчитать Sp+Sm
if (Sp < 0) Sp = 0; // выбрать максимум из S(B), S(BMP)
}
return S; // вернуть максимальную сумму
2IS: Поиск индексов допиши сам. Hе забудь проверку на случай, когда
последовательность пуста или не содержит положительных элементов.
С уважением, Олег Полубасов. СПб.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
поиск подмассива с максимальной суммой элементов