>Надо найти подпоследовательность (без разрывов) с максимальной суммой.

Может я что-то не понимаю. А сколько элементов имеет эта подпоследовательность, сумму которой надо найти?

Сколько угодно, в том числе и ноль. Просто в последовательности могут быть отрицательные числа.

foreach(@m){
  $h{$count}+=$_ if $_>0;
  $count++ if $_<0;
}

потом хеш сортируется по значению 

Это, как я понял, выделение максимальной подпоследовательности с положительными членами? Тогда если задана 3,4,-1,5,6 то выделится 5,6 а надо все выделить, у них сумма больше. Или я что-то не так понял?

я последовательно члены перебираю, если они положительные то плюсуются в хеш, пока положительные плюсуются в хеш с ключем $count, как только появился хотябы один отрицательный член, $count увеличивается нна единицу, как только снова положительный - члены последовательности плюсуются в хеш с ключем $count;

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

тогда я не понимаю, чем ограничены подпоследовательности? отр. числами или выделить макс подпосл. включающую отр числа... это писать надо а мне ишо работка на завтра...

Задача полностью изложена в первых двух строках первого поста. Мне алгоритм нужен, программировать я умею неплохо. Подпоследовательность ничем не ограничена. Ладно, попробую более формально сформулировать задачу. Итак
a1, a2, ..., an - исходная последовательность, ai - любое
Задача: найти i и j (1 <= i <= j <= n) такие, что
(ai + a{i+1} + ... + a{j-1} + aj) >= (ak + a{k+1} + ... + al) для любых 1 <= k <= l <= n

Вроде ничего не перепутал

Ну и 1 <= n <= 1000000

Добрый вечер.
Искомая последовательность находится за один проход по всему массиву,
сложность O(n).
Решение у меня такое:

Суммируем последовательно все члены, запоминая максимальную сумму и
номера первого и последнего членов последовательности с максимальной
суммой. Если на очередном шаге сумма оказалась отрицательной, то
сбрасываем сумму в ноль и считаем, что следующий элемент - первый в
последовательности. Когда дойдём до последнего элемента, запомненные
границы последовательности с максимальной суммой дают искомую
последовательность.

На примере:

Границы последовательности обозначаем так:
[номер_первого_элемента, номер_последнего_элемента]
Дана последовательность:
3 -2 4 -1 -3 6 -20 5 1 -4 43 -5 3

начинаем суммировать:
1.  сумма 3,  границы [1, 1] (последовательность "3")
    это первая сумма, принимаем её за максимальную:
    макс = 3, границы [1, 1]
2.  сумма 1,  границы [1, 2] (последовательность "3 -2")
3.  сумма 5,  границы [1, 3] (последовательность "3 -2 4")
    это макс. сумма, запоминаем:
    макс = 5, границы [1, 3]
4.  сумма 4,  границы [1, 4] (последовательность "3 -2 4 -1")
5.  сумма 1,  границы [1, 5] (последовательность "3 -2 4 -1 -3")
6.  сумма 7,  границы [1, 6] (последовательность "3 -2 4 -1 -3 6"
    это макс. сумма, запоминаем:
    макс = 7, границы [1, 6]
7.  сумма -13 - отрицательная сумма, "сбрасываем" последовательность
8.  сумма 3,  границы [8, 8] (последовательность "5")
9.  сумма 6,  границы [8, 9] ("5 1")
10. сумма 2,  [8, 10] ("5 1 -4")
11. сумма 45, [8, 11] ("5 1 -4 43")
    это макс. сумма
    макс = 45, границы [8, 11]
12. сумма 40, [8, 12] ("5 1 -4 43 -5")
13. сумма 43, [8, 13] ("5 1 -4 43 -5 3")

Итак, макс. сумма = 45, для посл-ти "5 1 -4 43"

Изучайте на здоровье :) Сейчас постараюсь сваять доказательство

2Legioner:

1. А cами числа какие? Целые (если да, то чем ограничены), FP?

2. Я не понял, зачем учитывать a[n+1] в max(a[n], a[n+1], a[n+2])? Я так понимаю, надо проходить только по положительным a[n] и сравнивать a[n] + a[n+1] + a[n+2] и max(a[n], a[n+2]).

2erDiZz (21.09.2005 21:20:51):

Да, похоже на истину.

И, поскольку O(n), то более короткого алгоритма, очевидно, нет, независимо от ограничений на числа.

это как-бы интуитивно понятно. бумажное доказательство, пригодное для изложения в форуме у меня как-то не складывается, хотя противоречий, вроде как, нет ...по крайней мере не за 15 минут, так что оставим это автору темы :)

Для того, чтобы получить решение O(n) (а оно возможно!),
нужно действовать примерно так: берем первый элемент, объявляем
его началом некоторой последовательности, заносим это значение
в список.

Для всех остальных элементов действуем чуть хитрее: если этот
элемент на 1 больше, чем хвост одной из наших существующих
последовательностей, то добавляем его к ней, иначе говорим
"этот элемент может стартовать последовательность" и вносим
эту новую последовательность в список.

В конце просто выбираем самую лучшую последовательность (а ее сумма
вычисляется, кстати, без всякого цикла :-))

Пример: исходная последовательность { 7 3 5 4 7 6 9 8 0 4 12 }

Алгоритм:

Шаг 1: берем 7 и добавлям в список последовательностей, на выходе имеем
такой список: { {7} }

Шаг 2: берем 3, 3 != 7+1, на выходе список последовательностей { {7} {3} }

Шаг 3: берем 5, 5!=7+1 и 5!=3+1, на выходе список { {7} {3} {5} }

Шаг 4: берем 4, видим что 4=3+1 и на выходе получаем { {7} {3,4} {5} }

Шаг 5: берем 7, видим что оно уже содержится в списке и забываем про нее

Шаг 6: берем 6, добавлйем в список как продолжение к 5, на выходе получаем { {7} {3,4} {5,6} }

Шаг 7: берем 9, никуда ее "присобачить" не можем, добавляем в список: { {7} {3,4} {5,6} {9} }

Шаг 8: берем 8, и видим, что можем приcоединить ее к 7, получаем { {7,8} {3,4} {5,6} {9} }

Шаг 9: берем 0, и начинаем c него новую последовательность { {7,8} {3,4} {5,6} {9} {0} }

Шаг 9: берем 4, видим что она уже использована, и забываем про нее

Шаг 10: берем 12, и начинаем с нее новую последовательность
(присобачить-то некуда!) и на выходе из алгоритма имеем
{ {7,8} {3,4} {5,6} {9} {0} {12} }

Вывод - лучшая из всех будет {7,8}

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

Цитата: "Подпоследовательность ничем не ограничена." :-)

на строгое описание надо смотреть

> Итак > a1, a2, ..., an - исходная последовательность, ai - любое > Задача: найти i и j (1 <= i <= j <= n) такие, что > (ai + a{i+1} + ... + a{j-1} + aj) >= (ak + a{k+1} + ... + al) для любых 1 <= k <= l <= n

если бы надо было искать максимально длинную послеовательность,
то задачка интереснее, можно получить алгоритм:
 с наилучшим временем O(N/2) 
 и худшим гарантированно меньшим O(N)

только я со значками постарался и она строгость потеряла >:) теперь в этом мире уже ничего не ясно. пора в гиперпространство..

кстати и эту можно ускорить до наилучшего O(N/2)

а вон ту - до O(ln (N)). и то не предел (можно конкретнее?)

anonymous (*) (21.09.2005 22:11:43):

> кстати и эту можно ускорить до наилучшего O(N/2)

Кстати, O(N/2)=O(N) :)

> на строгое описание надо смотреть

Если надо просто найти именно максимальную непрерывную
последовательность, и автор топика не сумел этого сделать...
Нет, тогда все совсем хреново в этом мире, раз уж люди не могут
написать даже такого примера:


[user@host] $ echo "1
2
3
4
3
4
5
6
1
2
3
4
5
6
7
8
9
10
2
3
4
5" | gawk 'BEGIN { bstart=0; bsum=0; blen=0; csum=0; cstart=0; cur=0; clen=0; }
{ if ($0!=1+cur) { if (csum>bsum) { bsum=csum; bstart=cstart; blen=clen; } ; cstart=FNR; csum=$0; cur=$0; clen=1; } else { csum+=$0; cur=$0; clen++; } }
END { if (csum>bsum) { bsum=csum; bstart=cstart; } ; print "Best starts from item["bstart"]"; print "Best sum is ["bsum"]"; print "Best length is "blen;}'
Best starts from item[9]
Best sum is [55]
Best length is 10
[user@host] $

2no-dashi (21.09.2005 22:44:00):

Все равно неверно :)

erDiZz (*) (21.09.2005 21:20:51) правильный алгоритм привел.

> Все равно неверно :)

Ну так блин какая постановка задачи, такое и решение. То ему надо выбрать {3,4,5,6} из {3,4,-1,5,6}, то вообще непойми что :-) Впрочем, можно в моем примере просто поменять $0=cur+1 на что-то вроде $0<0 - и получить правильный вариант :-)

вот такая последовательность:
1000, -1001, 1

очевидное решение - 1000
по Вашему алгоритму - 1

Все таки задача комбинаторная и решение должно быть больше O(n)

Задача упрощается заменой однознаковых интервалов их суммой
1,2,3,-4,-5,6,7,-8 -> 6, -9, 13, -8

А дальше перебор всех непрерывных подпоследовательностей ( O(N x N)

Извиняюсь за плагиат.
Помочь тут может только применение искусственного интеллекта (эволюционные алгоритмы, и т.п.) Но тогда достоверность результата не 100%

> Помочь тут может только применение искусственного интеллекта (эволюционные алгоритмы, и т.п.) Но тогда достоверность результата не 100%

Почем нынче трава?

> вот такая последовательность:
> 1000, -1001, 1

> очевидное решение - 1000
> по Вашему алгоритму - 1 

алгоритм верный, просто ты его, видимо, неправильно понял

едем для этой последовательности:
1) сумма 1000, после-ть "1000"
   это макс. сумма, макс = 1000
2) сумма -1, отрицательная, сбрасываем последовательность
3) сумма 1, посл-ть "1"

итого макс=1000, для последовательности "1000"

это же так просто

Используй в качестве подалгоритма алгоритм скользящей суммы. Т.е. если последовательность длинной в N, а подпоследовательность - m вычисляешь сумму 1-х m членов последовательности sum(1,m). Вторая сумма вычисляется проще (т.е. sum для x(2)...x(m+1)): sum(2,m)=sum(1,m)-x(1)+ x(m+1). Основной алгоритм начинаешь с m=1. Здесь запоминаешь y=sum(1,1). На следующем проходе sum(1,2)=y+x(2). Дальше надеюсь разжевывать не надо, что с чем сравнивать.

Наверно плохо описал идею. Поэтому дам примерчик на питоне.
К слову, отделять участки по признаку положительные/отрицательные
нельзя это видно на примере 
сумма (5,6,7,-8,9) больше суммы (5,6,7)
или по признаку положительная/отрицательная сумма,
а если в последовательности все числа отрицательные?
==========================================
# M - размер подпоследовательности
# n - индекс первого элемента
# summ - текущая сумма

x=(1,-2,3,-4,5,6,7,-8,9,0) # последовательность
mmax=x[0] # здесь храним максимум
M=1
n=0


y=0  # 1-е значение для скользящей суммы
for m in range(1,len(x)+1):
	y = y + x[m-1]	# наращиваем 1-е значение 
			# для скользящей суммы 
			# подпоследовательности
			# из m элементов
	summ = y
	if mmax < summ:
		mmax = summ
		M = m
		n = 0
	# скользящая сумма
	for j in range(m,len(x)):
		summ = summ - x[j-m] + x[j]
		if mmax < summ:
			mmax = summ
			M = m
			n = j-m+1

print "sum(%d,%d) = %d" % (n,M,mmax)

Об чем спор-то?

Алгоритм, предложенный erDiZz (21.09.2005 21:20:51), верный и дает кратчайшее (по асимптотике) возможное решение.

erDiZz сделал, как минимум, два допущеня.
1) последовательность коррелирована
2) подпоследовательности не имеют общих элементов

2kosmonavt(*) (22.09.2005 15:19:12):

erDiZz сделал одно допущение: что есть хотя бы один неотрицательный элемент. Если допускаются последовательности, состоящие только из отрицательных чисел, то алгоритм тривиально обобщается.

> 1) последовательность коррелирована

...и эмбрионирование модальности коллапсирует синусоидально ;)

> 2) подпоследовательности не имеют общих элементов

Сдается мне, кто-то из нас двоих чего-то не понимает. Может, конечно, я...

Можно пример:

Исходная последовательность; верный ответ; неверный ответ, выданный алгоритмом erDiZz?

алгоритм не работает для массива отрицательных чисел.

Большое спасибо всем.

Наверное алгоритм данный erDiZz правильный, сейчас подумаю над его обоснованием.

2 kosmonavt я знаком с этим методом, но ваше решение на питоне, насколько я понимаю, имеет сложность O(n*n) (потому что 2 цикла), это не то, что я хотел.

>Если допускаются последовательности, состоящие только из отрицательных чисел, то алгоритм тривиально обобщается.

Согласен. С остальным тоже. Не увидел тривиального обобщения на отрицательной последовательности и ушел за "тучу".

sarg (22.09.2005 16:34:14):

> алгоритм не работает для массива отрицательных чисел.

Да все работает...

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

Вообще-то максимальная сумма для массива из отрицательных чисел - это максимальное число. ))

http://www.lib.csu.ru/dl/text/programm/info/1kurs/bentli/002.htm

читать с пункта 8.1
разобраны 4 алгоритма решения этой задачи

За ссылку спасибо. Буду читать. С доказательством у меня проблемы =) Я поступил проще - в одной программе для одного случайного массива сначала делаю полный перебор и нахожу 100% правильное решение, потом проверяю вышеупомянутым методом, вроде всё нормально работает, по крайней мере на последовательностях длины 1000 уже пару тысяч раз всё нормально прошло.

так. алгоритм, который я привёл, на последовательности из одних отрицательных чисел _работает. для наглядности можно добавить проверку максимальности текущей суммы в момент сброса на ноль - тогда вся неясность по поводу "только отрицательных" снимется.

Отрицательные числа

> В качестве начальной максимальной суммы надо взять первый элемент. Текущую сумму надо сравнивать с максимальной _независимо_ от того, больше нуля текущая сумма или меньше.

В качестве начальной нужно брать пустую последовательность (0 элементов). Соответственно, её сумма равна нулю.

>В качестве начальной нужно брать пустую последовательность

Это лишнее. Тогда получается, что для отрицательной последовательности максимальным значением будет 0.

В качестве начальной суммы логично взять 1 << (sizeof(int)*8-1)

>В качестве начальной суммы логично взять 1 << (sizeof(int)*8-1)

Хм. Я вас тут с отрицательными числами основательно запутал. Вполне достаточно первого описания этого алгоритма.

> В качестве начальной суммы логично взять 1 << (sizeof(int)*8-1)

и всё же нет ничего более корректного, чем взять за начальную сумму значение первого числа последовательности