:: Игры Разума
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Маловато будет. Еще одного внутреннего цикла не хватает.
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Сейчас нет времени подробно писать. Вобщем, решение такое
s1=-1000
s2=-1000
SCAN
s2=MAX(f1,s2+f1)
s1=MAX(s1,s2)
ENDSCAN
?s1
Вечером напишу подробнее.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Prudivus
Маловато будет. Еще одного внутреннего цикла не хватает.
Был неправ. Вспылил. (с)
Все работает, скорость сравнимая. Но, признаться, пока так и не понял почему.
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Игорь!

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

Хорошей скорости можно достичь, если количество выполняемых действий будет пропорционально N, где N - это число элементов в последовательности (в крайнем случае сошло бы и N*ln(N), но в данном случае у нас получится именно N). Этого можно достичь, если в цикле, который пробегает по всем элементам последовательности, количество выполняемых действий не будет зависеть от n. А этого можно достичь только, если на каждом шаге научиться использовать расчеты, проведенные на предыдущем шаге. Например, допустим мы знаем требуемую сумму для последовательности, состоящей из n элементов, не поможет ли нам эта информация рассчитать требуемую сумму, если к этой последовательности добавить еще один элемент. Как нетрудно догадаться, для новой последовательности эта сумма будет или такой же, или больше. Опять же понятно, что в последнем случае в сумму обязательно будет входить вновь добавленный элемент. Т.е. сумма для последовательности из n+1 элементов будет или равна сумме для последовательности из n элементов, или максимальной сумме элементов, с некоторого элемента и до конца последовательности, собственно нужная сумма будет максимум из этих двух чисел. Жаль только, что для того, чтобы посчитать второе число опять-таки нужно выполнить слишком много вычислений. А нельзя ли и тут попробовать использовать то, что уже вычислено на предыдущем шаге. Допустим, нам известна максимальная сумма с участием последнего элемента для последовательности с n элементами. Оказывается, что для последовательности с добавленным элементом для такой суммы возможны тоже только два варианта: или она будет равна сумме от предыдущей последовательности + последний добавленный элемент, или она будет равна самому последнему добавленному элементу, в зависимости от того, какое из этих двух чисел больше. Получается, что зная две суммы (искомую сумму и такую же сумму с условием включения последнего элемента) для последовательности из n элементов, мы легко и быстро можем найти эти же суммы для последовательности с еще одним добавленным элементом. Поскольку для последовательности, состоящей из одного элемента ити суммы равны самому элементу, то все остальное - дело техники. В результате получаем следующий код
s1=-1000
s2=-1000
SCAN
s2=MAX(f1,s2+f1)
s1=MAX(s1,s2)
ENDSCAN
?s1
Здесь s1 - это текущее значение искомой суммы, а s2 - текущее значение суммы с условием включения последнего элемента.
В SQL-ном варианте у меня этот алгоритм выглядит так
SELECT RECNO() as rn, f1, CAST(0 as N(14,4)) as s1, CAST(0 as N(14,4)) as s2 ;
FROM tmp INTO CURSOR tmp1 READWRITE
UPDATE tmp1 SET s2=IIF(NVL(t.s2,-1000)<=0,tmp1.f1,t.s2+tmp1.f1), s1=IIF(NVL(t.s1,-1000)<tmp1.s2, tmp1.s2, t.s1) ;
from tmp1 left join tmp1 t on tmp1.rn=t.rn+1
SELECT tmp1
GO BOTTOM
?tmp1.s1
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Все равно это фокус. Простота кода восхищает, но объяснения ничего, по сути, не объясняют. По крайней мере для меня.

Леонид, если можно, то же самое, но без лирики и чуть больше математики в доказательстве... Но именно чуть, без фанатизма! ;)
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Вот так вот понятней будет?

Пусть задана последовательность
a1, a2, ... aN
Положим
s(k,m)= ak+ ak+1+...+ am, где m Є (1,N), k Є (1,m),
P(m)=Max(s(k,m)) по всем k Є (1,m),
S(m)=Max(P(k)) по всем k Є (1,m).
Тогда, очевидно, что S(1)=P(1)=a1
Далее пойдем по индукции. Предположим, что для некоторого k Є (1,N), P(k) и S(k) уже вычислены и попробуем, зная эти значения, вычислить P(k+1) и S(k+1). Не стану объяснять подробно, но нетрудно понять, что P(k+1) будет равно P(k)+ ak+1, если P(k)>0, и будет равно ak+1, если P(k)<=0, а это то же самое, что P(k+1)=Max(P(k)+ ak+1, ak+1). А из определения видно, что S(k+1)=Max(S(k), P(k+1)). Вот эти формулы собственно и запрограммированы. S(N) – это то значение, которое требуется найти.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Igor Korolyov
Автор

Сообщений: 34580
Дата регистрации: 28.05.2002
Привет Леонид!

Они похожи но не идентичны - у тебя отсечение "плохого" хвоста реализовано алгоритмически проще (зато логически сложнее - в смысле понять это сложнее )... Ты отсекаешь его просто сравнивая полную сумму (хвост+новое число) с новым числом. Я же делаю отсечение за 1 шаг до того, сравнивая полную сумму с 0 - ну т.е. когда очевидно что сумма будет плохая (отрицательная) и хвост надо резать


------------------
WBR, Igor
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 3 (Гостей: 3)

© 2000-2024 Fox Club 
Яндекс.Метрика