Максимальная несегментная сумма

Question

У нас есть список/массив чисел (положительные и отрицательные значения возможны).

Сегмент определяется как смежная подпоследовательность цифр. Например, [1; -2; 3; 4; 5] - это массив, а его сегмент - [1; -2; 3] или [-2; 3; 4] и т. Д. Все числа в сегменте должны быть смежным.

Не-сегмент определяется как все подпоследовательности массива, за исключением всех сегментов. Таким образом, смежные числа возможны в несегменте, но должно быть не менее двух чисел, которые не являются смежными.

Например, [1; 3; 4] не является сегментом, [1; -2; 3; 5] также является несегментным, поскольку 3 и 5 не являются смежными (имеется «4», между ними в исходном массиве).

Вопрос в том, что представляет собой несегмент, имеющий максимальную сумму?

---

Примечание

1. Числа могут быть сочетание позитивы и негативы
2. Это не проблема http://algorithmsbyme.wordpress.com/2012/07/29/amazon-interview-question-maximum-possible-sum-with-non-consecutive-numbers/ или Maximum sum of non consecutive elements. В этих проблемах никакие числа не могут быть смежными и все числа положительны.

---

Это проблема 11 в книге Pearls of functional algorithm design и говорит, что есть линейный способ решить.

Но я не могу понять и не найти линейный путь. Поэтому я стараюсь здесь.

Answer 1

Вот решение, более подходящее для идиомы функционального программирования. Можно представить себе конечный автомат с четырьмя состояниями, который принимает строки, имеющие два несмежных 1s.

 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' 

Answer 2

Возьмите все положительные числа. Если они образуют сегмент, проверьте, можете ли вы добавить что-то не рядом с ним. Также проверьте, можете ли вы выбрать что-то в середине. Также проверьте, можете ли вы снять конец и поставить рядом с ним номер. Не сложно доказать, что один из них ведет к лучшему несегменту.

Answer 3

Есть 2 варианта:

• Там существует в большинстве 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.

  Обратите внимание, что мы можем сделать любое из условий максимальной суммой, просто изменив значение, таким образом, все условия необходимы.