algorithm - 最大非段总和

我们有一个数字列表/数组（正数和负数都是可能的）。
段被定义为数字的连续子序列例如，[1；-2；3；4；5]是数组，它的一段是[1；-2；3]或[-2；3；4]等。段中的所有数字都必须是连续的。
非段定义为数组的所有子序列，所有段除外。因此，在非段中可以有连续的数字，但必须至少有两个不连续的数字。
例如，[1；3；4]是非段，[1；-2；3；5]也是非段，因为3和5不连续（在原始数组中它们之间有一个“4”）。
问题是什么非分段具有最大和？
注意
数字可以是正数和负数的混合。
这不是http://algorithmsbyme.wordpress.com/2012/07/29/amazon-interview-question-maximum-possible-sum-with-non-consecutive-numbers/或Maximum sum of non consecutive elements的问题在这些问题中，没有数字可以是连续的，所有数字都是正的。
这是书中的问题11，它说有一个线性的方法来解决它。
但我不明白也找不到线性的方法所以我在这里试试运气。

最佳答案

这里有一个更适合函数式编程习惯用法的解决方案我们可以想象一个四态有限自动机，它接受具有两个非相邻1的字符串。

       0         1         0         0,1
      ___       ___       ___        ___
     v  /  1   v  /  0   v  /  1    v  /
---> (q0) ---> (q1) ---> (q2) ---> ((q3))

下面的Haskell程序基本上是一次扫描一个数字，并记住通过选择的最大值，当被解释为0和1时，将自动机置于状态q1（segmentEndingHere）、状态q2（segmentNotEndingHere）或状态q3（nonSegment）。这项技术是一个大锤，它可以解决许多关于序列优化的问题。

maximumNonSegmentSum :: (Num a, Ord a) => [a] -> Maybe a
maximumNonSegmentSum = mnss Nothing Nothing Nothing
  where
        (^+) :: (Num a) => a -> Maybe a -> Maybe a
        (^+) = liftM . (+)

        mnss ::
             (Num a, Ord a) => Maybe a -> Maybe a -> Maybe a -> [a] -> Maybe a
        mnss segmentEndingHere segmentNotEndingHere nonSegment xs
          = case xs of
                [] -> nonSegment
                x : xs'
                  -> mnss ((x ^+ segmentEndingHere) `max` Just x)
                       (segmentNotEndingHere `max` segmentEndingHere)
                       (((x `max` 0) ^+ nonSegment) `max` (x ^+ segmentNotEndingHere))
                       xs'