Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Маловато будет. Еще одного внутреннего цикла не хватает.
|
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Сейчас нет времени подробно писать. Вобщем, решение такое
|
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Был неправ. Вспылил. (с) Все работает, скорость сравнимая. Но, признаться, пока так и не понял почему. |
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Игорь!
Вчера вечером посмотрел твой алгоритм, и конечно-же и твой и мой алгоритмы по-существу идентичны. Главная разница в том, как объясняется, что полученный результат - это то, что нужно. Попробую более ли менее подробно изложить свои рассуждения. Хорошей скорости можно достичь, если количество выполняемых действий будет пропорционально N, где N - это число элементов в последовательности (в крайнем случае сошло бы и N*ln(N), но в данном случае у нас получится именно N). Этого можно достичь, если в цикле, который пробегает по всем элементам последовательности, количество выполняемых действий не будет зависеть от n. А этого можно достичь только, если на каждом шаге научиться использовать расчеты, проведенные на предыдущем шаге. Например, допустим мы знаем требуемую сумму для последовательности, состоящей из n элементов, не поможет ли нам эта информация рассчитать требуемую сумму, если к этой последовательности добавить еще один элемент. Как нетрудно догадаться, для новой последовательности эта сумма будет или такой же, или больше. Опять же понятно, что в последнем случае в сумму обязательно будет входить вновь добавленный элемент. Т.е. сумма для последовательности из n+1 элементов будет или равна сумме для последовательности из n элементов, или максимальной сумме элементов, с некоторого элемента и до конца последовательности, собственно нужная сумма будет максимум из этих двух чисел. Жаль только, что для того, чтобы посчитать второе число опять-таки нужно выполнить слишком много вычислений. А нельзя ли и тут попробовать использовать то, что уже вычислено на предыдущем шаге. Допустим, нам известна максимальная сумма с участием последнего элемента для последовательности с n элементами. Оказывается, что для последовательности с добавленным элементом для такой суммы возможны тоже только два варианта: или она будет равна сумме от предыдущей последовательности + последний добавленный элемент, или она будет равна самому последнему добавленному элементу, в зависимости от того, какое из этих двух чисел больше. Получается, что зная две суммы (искомую сумму и такую же сумму с условием включения последнего элемента) для последовательности из n элементов, мы легко и быстро можем найти эти же суммы для последовательности с еще одним добавленным элементом. Поскольку для последовательности, состоящей из одного элемента ити суммы равны самому элементу, то все остальное - дело техники. В результате получаем следующий код
В SQL-ном варианте у меня этот алгоритм выглядит так
|
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Все равно это фокус. Простота кода восхищает, но объяснения ничего, по сути, не объясняют. По крайней мере для меня.
Леонид, если можно, то же самое, но без лирики и чуть больше математики в доказательстве... Но именно чуть, без фанатизма! ;) |
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) – это то значение, которое требуется найти. |
Re: Максимум суммы | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Леонид!
Они похожи но не идентичны - у тебя отсечение "плохого" хвоста реализовано алгоритмически проще (зато логически сложнее - в смысле понять это сложнее )... Ты отсекаешь его просто сравнивая полную сумму (хвост+новое число) с новым числом. Я же делаю отсечение за 1 шаг до того, сравнивая полную сумму с 0 - ну т.е. когда очевидно что сумма будет плохая (отрицательная) и хвост надо резать ------------------ WBR, Igor |
© 2000-2024 Fox Club  |