最大非细分总和

我们有一个数字列表（，肯定和否定都是可能的）。最大非细分总和

段被定义为连续的子序列的数字。例如，[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问题。在这些问题中，没有数字可以连续，所有数字都是正数。

这是本书Pearls of functional algorithm design问题11和它说是解决它线性方式。

但我不明白，也没有找到一个线性的方式。所以我在这里尝试我的运气。

来源

2014-01-09 Jackson Tale

下面是一个更适合功能性编程习惯用法的解决方案。可以想象一个接受具有两个不相邻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'

来源

2014-01-13 16:40:52

我在你的回答之前就想出了那本书的出路。谢谢。此外，我认为这种功能性的方式是最好的想法，也将有助于强制性的方式。你读过那本书吗？ –

取所有正数。如果他们形成一个细分市场，请检查您是否可以添加不相邻的东西。另外检查一下你是否可以在中间选择一些东西。此外，请检查您是否可以结束并在旁边输入号码。证明其中之一导致最佳的非细分市场并不难。

来源

2014-01-10 00:33:47 tmyklebu

有以下两种方式：

最多2个非负数存在着，并且，在2的情况下存在，他们正在邻国。

在这种情况下，我们挑选最大的一对非相邻数字。这可以通过查找最大数目和具有最大非相邻数字的总数以及其两个相邻数字之和的线性时间来完成。

实施例：
```
Input: [-5, -10, -6, -2, -1, -2, -10] 
```
数量最多是-1，因此我们总结-1和最大的非相邻数（-5），这给-6。然后我们也尝试-2和-2，给出-4。所以最大的非细分总和是-4。
存在至少两个非相邻的非负数。

我们挑选所有正数。如果最大的数字是零（即没有正数），那么选择所有的零。

如果所有的挑选号码是连续的，尝试：
- 排除最小的一个，这不是在末端之一。
- 包括与选取的数字不相邻的最大（即最接近0）的非正数（如果存在这样的0，这将是最佳选项）。
- 反过来，尝试排除序列末尾的数字，然后在其旁边包含非正数（只有在旁边存在数字时才进行此操作）。
选择这里给出最大的总和。

很明显，所有这些都可能发生在线性时间。

例子：
```
Input: [-5, -1, 5, 7, 9, 11, -1, -10] 
```
所以首先我们选择所有正数 - 5, 7, 9, 11，但他们是连续的。

所以我们尝试排除最小的非最终号码（7），
给我们sum(5, 9, 11) = 25。

然后，我们尝试包括最大的非相邻负数（-5），
给我们sum(-5, 5, 7, 9, 11) = 27。

然后我们尝试排除左边缘（5），并包括未来数它（-1），
给我们sum(-1, 7, 9, 11) = 26。

然后我们尝试排除右边缘（11），并包括未来数它（-1），
给我们sum(-1, 5, 7, 9) = 20。

显然最大的总和是27。

请注意，我们可以通过只更改一个值来使任何条件达到最大值，因此需要所有条件。

来源

2014-01-10 00:40:59 Dukeling

最大非细分总和

回答

相关问题