intのセリフで可能な最も低い値を見つける方法は？

Question

は、私はこの1つのように（正と負）の整数の配列を有する：

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

をそして、私は（そしてもちろん、最悪の結果を見つけることが可能（値の小さい方の和）このシーケンスのいずれかのサブシーケンスを服用する必要がありますそのサブシーケンスの開始インデックスと終了インデックス）。

これは、2^nではない（すべての可能なシーケンスを1つずつ計算する）方法はありますか？

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

値の小さい方の和がサブであろう：

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

Answer 1

最小値を見つける問題により最大検索に変換することができるこの簡単な配列と例えば

、各項目の記号を変更する。最大サブシーケンスについては、周知のアルゴリズムが存在する（例えば、特許文献1参照）。 here。

元のリストを操作するには、リストを変換して前記アルゴリズムを適用するか、アルゴリズム自体をわずかに変更します（プラスではなく最大またはマイナスの最小値）。