Как найти самое низкое значение из серии ints?

Question

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

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) 

Answer 1

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

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

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