Алгоритм для нахождения максимальной подпоследовательности массива положительных чисел. Выгода: Никакие смежные элементы не позволяются

Ответ Chris перестал работать в списке [9,10,9], производя 10 вместо 9+9 = 18.

Joe не совсем прав. Коммивояжер требует, чтобы Вы посетили каждый город, тогда как нет никакого аналога к этому здесь.

Одно возможное решение было бы рекурсивным решением:

function Max_route(A)
    if A's length = 1 
        A[0]
      else
        maximum of
          A[0]+Max_route(A[2...])
          Max_route[1...]

Это имеет то же, большое-O как наивная функция fibonacci, и должно уступить части той же оптимизации (например, memoization), если Вы заботитесь об эффективности в дополнение к простому получению корректного ответа.

- MarkusQ

[Редактирование]---

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

Вы могли обернуть функцию выше так, чтобы она только вычислила значение для каждого массива однажды (в первый раз, когда это назвали), и на последующих вызовах просто возвратит сохраненный результат. Это взяло бы O (n) пространство, но возвратится в постоянное время. Это означает, что целый алгоритм возвратил бы в O (n) время, лучше, чем экспоненциальное время менее нарушенной версии выше. Я предполагал, что это было хорошо понято.

[Второе редактирование]------------------------------

, Если мы разворачиваем вышеупомянутое немного и дразним его независимо, мы добираемся:

f []      :- [],0
f [x]     :- [x],x
f [a,b]   :- if a > b then [a],a else [b],b
f [a,b,t] :- 
    ft = f t
    fbt = f [b|t]
    if a + ft.sum > fbt.sum
        [a|ft.path],a+ft.sum
      else
        fbt

, Который мы можем развернуть в псевдо основной использующий только размер n массивы целых чисел и булевских переменных и операций 1) индексации массива и присвоения индексного массива, 2) целочисленной математики, включая сравнение, 3) if/then/else и 4) одного единственного цикла O (n):

dim max_sum_for_initial[n],next_to_get_max_of_initial[n],use_last_of_initial[n]

max_sum_for_initial[0] = 0
next_to_get_max_of_initial[0] = -1
use_last_of_initial[0] = false

max_sum_for_initial[1] = a[0]
next_to_get_max_of_initial[1] = -1
use_last_of_initial[1] = true

if a[0] > a[1]
    max_sum_for_initial[2] = a[0]
    next_to_get_max_of_initial[2] = 0
    use_last_of_initial[2] = false
  else
    max_sum_for_initial[2] = a[1]
    next_to_get_max_of_initial[1] = -1
    use_last_of_initial[2] = true

for i from 3 to n
    if a[i]+max_sum_for_initial[i-2] > max_sum_for_initial[i-1]
        max_sum_for_initial[i] = a[i]+max_sum_for_initial[i-2]
        next_to_get_max_of_initial[i] = i-2
        use_last_of_initial[i] = true
      else
        max_sum_for_initial[i] = max+sum_for_initial[i-1]
        next_to_get_max_of_initial[i] = i-1
        use_last_of_initial[i] = false

В конце мы можем извлечь результаты (в обратном порядке):

for i = n; i >= 0; i = next_to_get_max_of_initial[i]
    if use_last_of_initial[i] then print a[i]

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

, я надеюсь, что это достаточно ясно.

- MarkusQ

Это - O (n).

Рекурсивный ответ в странном псевдокоде Prologesque:

maxSum([]) = 0
maxSum([x]) = x
maxSum(A) = max(A[0] + maxSum(A[2..n]),
                A[1] + maxSum(A[3..n]))

С соответствующей обработкой индексов из диапазона.

Редактирование: Это уменьшает до более хорошего ответа MarcusQ:

maxSum([]) = 0
maxSum(A) = max(A[0] + maxSum(A[2..n]), maxSum(A[1..n]))

Редактирование: Вот версия, которая возвращает фактическую подпоследовательность, а не просто ее сумму. Это превышает лимиты моей специальной pseudo-Prolog-C химеры, таким образом, я остановлюсь теперь.

maxSub([]) = []
maxSub(A) = sub1 = [A[0]] + maxSub(A[2..n])
            sub2 = maxSub(A[1..n])
            return sum(sub1) > sum(sub2) ? sub1 : sub2

ответ @MarkusQ как острота Python (измененный как @recursive предложенный в комментариях):

f = lambda L: L and max([L[0]] + f(L[2:]), f(L[1:]), key=sum)

Пример:

>>> f([1,51,3,1,100,199,3])
[51, 1, 199]

Это неэффективно, но Это могло бы использоваться для тестирования более быстрых решений.

То же - в Emacs Lisp

(defun maxsubseq (L)
  "Based on MarkusQ's and sth's answers."
  (if (not L) L
    (let ((incl (cons (car L) (maxsubseq (cddr L))))
          (excl (maxsubseq (cdr L))))
      (if (> (sum incl) (sum excl)) incl excl))))

(defun sum (L) (apply '+ L))

Повторяющаяся версия (O (N), если хвостовая рекурсия доступна)

Она основана ответ @sth :

(defun maxsubseq-iter-impl (L excl incl)
  (let ((next (if (> (car excl) (car incl)) excl incl)) (x (car L)))
    (if (not L) (cdr next)
      (maxsubseq-iter-impl (cdr L) next
                           (cons (+ x (car excl)) (cons x (cdr excl)))))))

(defun maxsubseq-iter (L) (reverse (maxsubseq-iter-impl L '(0) '(0))))

Пример:

(require 'cl)
(loop for f in '(maxsubseq maxsubseq-iter) 
      collect (loop for L in '((1 51 3 1 100 199 3) (9 10 9)) 
      collect (f L)))

Вывод:

(((51 1 199) (9 9)) ((51 1 199) (9 9)))

При использовании набора необычных слов это не в основном просто простая проблема графика коммивояжера?

Кроме этого случая Вы ищете самый дорогой маршрут через (плотный) график? В этом случае вершины являются просто самими числами, края не направлены и не имеют никакого веса, и все вершины соединены, кроме к вершинам, которые были смежны с ними в исходном списке?

макс. (oddIndexSum, evenIndexSum) не работает

Для примера, который Вы дали, он делает - однако, если у Вас есть что-то как: A = [1, 51, 3, 2, 41, 23, 20], Вы можете иметь 51 + 2 + 23 = 76, или Вы можете иметь 51 + 41 + 20 = 112, который ясно больше, и избегает смежных элементов также. Это то, что Вы ищете?

Редактирование: Это - действительно простофиля sth's, но я не понял это, пока я не отправил его.

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

Псевдокод:

sum_excluded_last_item= 0
sum_included_last_item= 0

for each item in list
    if (item>0)
        last_sum_excluded_last_item= sum_excluded_last_item
        sum_excluded_last_item= max(sum_included_last_item, sum_excluded_last_item + item)
        sum_included_last_item= last_sum_excluded_last_item + item
    else
        sum_excluded_last_item= max(sum_excluded_last_item, sum_included_last_item)
        sum_included_last_item= sum_excluded_last_item

max_sum= max(sum_excluded_last_item, sum_included_last_item)

Получение фактического списка является осуществлением, оставленным до читателя. Или меня, если Вы добавляете больше комментариев. Но это должно быть очевидно из алгоритма.

Мы можем использовать вспомогательный массив B [0.. n-1], где B [я] - максимальная сумма элементов [0.. i] и C [0.. n-1], где C [я] - булево сообщение, если [я] находится в максимальной подпоследовательности суммы:

B[0]=max(A[0],0); C[0]=(A[0]>0)
B[1]=max(B[0],A[1]); C[1]=(A[1]>B[0])
for i in [2..n-1]
  if A[i]+B[i-2] > B[i-1]
      C[i]=True
      B[i]=A[i]+B[i-2]
  else
      C[i]=False
      B[i]=B[i-1]
mssq=[]
i=n-1
while i>=0
  if C[i]
    push(A[i],mssq)
    i=i-2
  else
    i=i-1
return mssq

Это ясно работает в O (n) время и пространство. На самом деле это совпадает с решением MarcusQ, только инвертированным и оптимизированным.

Для предотвращения рекурсии мы можем взять от реверса, чем вперед,

т.е.) для Массива [1.. n]->

     maxSum(A,n): for all n

         if n=0, maxSum = 0 else
         if n=1, maxSum=A[1] else
                maxSum = max(A[n] + maxSum(A,n-2), maxSum(A,n-1))

, Чтобы постараться не вычислять Max (A, n-2), при расширении maxSum (A, n-1), это может быть сохранено и вычислено. Именно поэтому я прошу инвертировать. т.е.) maxSum (A, n-1) = макс. ([n-1] + maxSum (A, n-3), maxSum (A, n-2)), где в Max (A, n-2) уже получен, и никакая потребность повторно вычислить) В otherwords вычисляют maxSum (A, n) для всего n, запускающегося от 1 до n, использующего выше формулы, чтобы не повторно вычислять.

т.е.) n=2, maxSum = макс. ([1] +maxSum (A, 0), maxSum (A, 1)) т.е.) n=3, maxSum = макс. ([2] +maxSum (A, 2), maxSum (A, 2)) и так далее.. и достигните последнего n., это будет o (n).

while you still have elements
     find the largest element, add it to the sum
     remove the element before and after the current

Код MarkusQ, похоже, полностью пропускает [2]. Я недостаточно умен, чтобы понять, где это должно фигурировать в расчетах.

Here is an answer done using dynamic programming using the same base concept as that used by MarkusQ. I am just calculating the sum, not the actual sequence, which can produced by a simple modification to this code sample. I am surprised nobody mentioned this yet, because dynamic programming seems a better approach rather than recursion + memoization !

int maxSeqSum(int *arr, int size) {
  int i, a, b, c;
  b = arr[0];
  a = (arr[1] > arr[0]) ? arr[1]: arr[0];
  for(i=2;i<size;i++) {
    c = (a > (b + arr[i]))? a : (b + arr[i]);
    b = a;
    a = c;
  }
  return a;
}