Cool Folders ® :: Форум Игротека :: Задача о ряде чисел

Задача о ряде чисел

Автор: Большой Грызь
Дата : 06-12-04, Пнд, 10:39:13

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

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)
[ 06-12-04, Mon, 17:45:40 Отредактировано: Большой Грызь ]

Задача о ряде чисел

№ 2

Автор: Большой Грызь
Дата : 07-12-04, Втр, 08:42:34

Никаких мыслей?

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задача о ряде чисел

№ 3

Автор: Pitek
Дата : 09-12-04, Чтв, 04:41:29

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

Задача о ряде чисел

№ 4

Автор: Большой Грызь
Дата : 09-12-04, Чтв, 08:16:41

Имеется в виду просто набор из N произвольных (необязательно целых) чисел идущих безо всякого порядка

П.С. имелся в виду чисто "геометрический" ряд (а-ля "стоящие один за другим"

) сорри, если ввел в заблуждение

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задача о ряде чисел

№ 5

Автор: Pitek
Дата : 09-12-04, Чтв, 11:05:37

ОК. Можно и за одир проход, но уж очень гоморойно в реализации.
Имеем на входе лист (массив) с числами. Бегаем по мену один раз.
Делаем сортированный лист, где ключ - номер. Делаем второй лист, где ключ - ключи на начало последовательности в сорт листе, в ноде также есть ключ на конец оной в сорт. листе и сумма.
Для каждого входящего числа делаются след. операции:
1. Вставить его в сорт. лист. Пройтись от вставленной позоции взад-вперед с целью выяснения начала и конце послед.
2. Изменить в листе-сумме ключи (если надо), и сумму.

После обработки всех входяших последная нода в листе-сумме и будет содержать искомую информацию.

P.S. Если вы поняли все, что я тут понаписал - я готов взять вас программером к себе в группу

Задача о ряде чисел

№ 6

Автор: Большой Грызь
Дата : 09-12-04, Чтв, 16:53:47

Стоп

Никаких сортированных листов

Это совершенно неоптимальное решение

Всё должно быть сделано за o(n) времени и за o(1) места

(на деле не просто за o(n) времени, а именно за одну проходку, а временных переменных достаточно 8 штук.. а если постараться, то и того меньше).

Так что никаких сортированных листов.
Кстати, алгоритм таки выходит достаточно красивым

точнее сама идея

П.С. вопрос на какую зарплату?

меня устраивают далеко не любые

П.П.С. тем более, что эту задачу решил за 10 минут

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)
[ 10-12-04, Fri, 0:03:56 Отредактировано: Большой Грызь ]

Задача о ряде чисел

№ 7

Автор: Tarlog
Дата : 11-12-04, Сбт, 02:05:22

Совсем просто...
Идея: максимальная сумма находится между 2 отрицательных чисел.
Алгоритм:
sum0 = 0;
Пока ряд не кончился {
Ищем первое не отрицательное число. Находим ставим пойнтер (р1)
Ищем следущее отрицательное число. Находим ставим пойнтер (р2) на последнее положительное.
В процессе поиска складываем положительные числа между р1 и р2, получаем sum1.
Если sum0 < sum1 {
r1=p1 r2=p2 sum0=sum1
}
}
Возвращаем r1 и r2 - пойнтеры на начало и конец.

Задача о ряде чисел

№ 8

Автор: Большой Грызь
Дата : 11-12-04, Сбт, 04:30:22

Неверно

Опровержение:

10 10 10 -1 10000 -1 10 10 10 -1 10 10 10

Твой алгоритм выдаст, что максимальная сумма = 10000.
А на самом деле максимальная сумма равна 10087 (весь ряд целиком)

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

Задача о ряде чисел

№ 9

Автор: Pitek
Дата : 12-12-04, Вск, 05:17:15

Только прочитав последний пост, до меня дошло, что я неправильно понял условеи и решал совсем другую задачу

Грызь, меня наши зарплаты вообще не устраивают