最大非細分總和

我們有一個數字列表（，肯定和否定都是可能的）。最大非細分總和

段被定義爲連續的子序列的數字。例如，[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

最大非細分總和

回答

相關問題