Есть такая задачка...
Дается последовательность целых чисел... Из нее надо выбрать подпоследовательность с максимальной суммой и возможно меньшей длины... Алгоритм перебора всех подпоследовательностей не принимается, надо сделать, что-нить быстрое и гениальное...
Я уверен, мы вместе это смогем...
Так что пишите... :0)

Цитата

выбрать подпоследовательность с максимальной суммой и возможно меньшей длины

Эти два условия противоречат друг другу, так что сперва давай конкретизируем, что же все-таки нужно сделать.

Да вроде смысл ясен.


Если ты имел ввиду это:
Имеется последовательность целых чисел. Требуется из нее выбрать последовательность определенной длины (меньшей длины исходной послед.), сумма элементов которой будет больше суммы ЛЮБОЙ другой последовательности (полученной из исходной) заданной длины (длина та же, что и у посл. с макс. суммой).

Тогда все просто. Ищи n наибольших чисел и запоминай их порядковый номер в массиве. Или запоминай в массиве сами эти числа.
Если напутал - извините.

Колво всех возможных послед. заданной длины выражается очень большими числами. Формулу лень выводить. А таким образом ты получишь послед. с макс суммой.

Цитата

Тогда все просто. Ищи n наибольших чисел и запоминай их порядковый номер в массиве. Или запоминай в массиве сами эти числа.

Ах, если бы все было так просто... :0(
Играющую роль в формировании последовательности играет сумма элементов... Но при все при этом, звиняйте что сразу не сказал, подполедовательностью в данном случае называется не выборка эл-тов из последовательности, а группа следующих друг за другом элементов..., т.е. из последовательности [1,-1,0,5,6,-3,0,5,-2] нельзя выбрать подпоследовательность [-1,5,6,-3], а надо [-1,0,5,6,-3]....
Думаем дальше...

P.S. Я уже думал, может какое трай-дерево строить?..

Ни у кого нет "Арсак. Программирование игр и головоломок"?
По-моему, там я видел решение подобной задачи в один проход.
Единственное, - не уверен, что было условие про минимальность длины...

Ну тогда простым перебором последовательностей. Иначе вроде никак.
Если тама по порядку, то пахать это бует довольно быстро.

Тут я подумал немного, и вот что пришло на ум... Можно сделать это в два пробега...
Первый пробег: Наращиваем сумму по всем элементам и запоминаем тот элемент на котором она максимальна...
Второй пробег(до максимума): Убираем из суммы элементы и запоминаем опять же максимум...
Вот так вроде бы должно работать... Но есть ведь и однопроходный алгоритм... Мож кто знает...

Я решал эту задачу два раза. Первый раз когда я был совсем маленький, тогда я вначале не понял, что надо в один проход, а когда узнал до решения не догадался. Второй раз пару лет назад - в один проход все правильно - тогда я еще удивился, что она так просто решилась. Сейчас решения не помню, но если не будет лень, придумаю снова.

А ну да. Алгоритм простой. Правда, как podval заметил - условие минимальности длины странное:
-1 -4 5 6 -2 -1 4 7 -3 2
и что отсюда выбрать?  5 6 -2 -1 4 7 или просто 5 6 или 4 7?
А алгоритм таков:
1. Находим первое положительное число и начинаем добавлять в нашу последовательность все элементы по порядку, пока не встретиться отрицательное.
2. Нашли отрицательное запоминаем позицию где его нашли и начинаем добавлять все элементы по порядку в специальную переменну - отрицательную сумму, пока не произойдет следующее: отрицательная сумма стала больше положительной - все сбрасываем и возвращаемся к п.1 Либо, мы наткнулись на положительный элемент. В этом случае запоминаем еще один индекс и начинаем накапливать вторую положительную сумму пока не встретим отрицательный элемент. Теперь сравниваем вторую положительную сумму и отрицательную - если положительная больше включаем весь промежуток, если нет, то если первая положительная сумма больше второй - то мы нашли наш интервал, иначе вторая сумма становиться первой и начинаем искать промежуток с того индекса который мы запомнили вторым.

Можно еще искать максимальный отрицателный элемент - если положительных не встретиться, то он будет искомым интервалом.

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

Еще раз всем огромноое спасибо, дали пищу для размышлений...

Alex 101: шли обязательно, мало ли что я сам накопаю?.. :0)

Я очень долго парился,но когда узнал решение ОФИГЕЛ:


sr:=0;
smax:=0;
for i:=0 to n do
begin
sr:=sr+a[i];
if sr<0 then sr:=0;
if sr>smax then smax:=sr;
end;
writeln(smax);



Приколите это ВСЕ! Работает 100%

P.S Обещенного 3 года ждут!!!!!!!!!!!!!!!!!!!!!!!!!!

Это сообщение отредактировал(а) B0BAH - 14.9.2005, 23:05