Как найти наименьшее возможное значение ряда целых чисел?

У меня есть последовательность целых чисел (положительных и отрицательных), подобная этой:

12,-54,32,1,-2,-4,-8,12,56,-22,-21,4,17,35

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

Есть ли способ сделать это, отличный от 2 ^ n (вычисляя все возможные последовательности один за другим)?

Например, с помощью этой простой последовательности:

1,2,-3,4,-6,4,-10,3,-2

Меньшая сумма значений будет подпоследовательностью:

-6,4,-10 (with start index 4 and end index 6)

sequence algorithm integer sequences
person Ignacio Soler Garcia    schedule 04.01.2012    source источник
comment
Под результатом вы подразумеваете суммирование значений в подпоследовательности?   -  person Howard    schedule 04.01.2012
comment
@ Ховард: да, спасибо за подсказку. Я буду редактировать.   -  person Ignacio Soler Garcia    schedule 04.01.2012
comment
Каким будет этот худший результат в вашем примере? -22, -21?   -  person fge    schedule 04.01.2012
comment
@fge: я отредактирую вопрос, чтобы было понятнее   -  person Ignacio Soler Garcia    schedule 04.01.2012
comment
вычисление всех возможных подпоследовательностей — это O(n^2), а не O(n^n).   -  person amit    schedule 04.01.2012
comment
@амит: согласен. Я снова отредактирую. Спасибо.   -  person Ignacio Soler Garcia    schedule 04.01.2012

Ответы (1)


arrow_upward
1
arrow_downward

Задача поиска минимума может быть преобразована в поиск максимума путем изменения знака каждого элемента.

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

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

person Howard    schedule 04.01.2012