I have a sequence of integers (positive and negative) like this one:
12,-54,32,1,-2,-4,-8,12,56,-22,-21,4,17,35
And I need to find the worst result (smaller sum of values) possible taking any sub sequence of this sequence (and of course the start index and end index of that sub sequence).
Is there a way of doing this that is not 2^n (computing all the possible sequences one by one)?
For example, with this simple sequence:
1,2,-3,4,-6,4,-10,3,-2
The smaller sum of values would be the subsequence:
-6,4,-10 (with start index 4 and end index 6)
The issue of finding the minimum can be transformed into a maximum search by changing sign of each item.
For the maximum subsequence there exist well-known algorithms, see e.g. here.
You can either transform your list and apply said algorithm or slightly modify the algorithm itself (min instead of max or minus instead of plus) in order to work with your original list.