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

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

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

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

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