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

Ответ 1

Построить максимальную подпоследовательность можно шаг за шагом, если вы сохраняете два состояния:

def maxsubseq(seq):
  # maximal sequence including the previous item
  incl = []
  # maximal sequence not including the previous item
  excl = []

  for i in seq:
    # current max excluding i
    if sum(incl) > sum(excl):
      excl_new = incl
    else:
      excl_new = excl

    # current max including i
    incl = excl + [i]

    excl = excl_new

  if sum(incl) > sum(excl):
    return incl
  else:
    return excl


print maxsubseq([1,4,6,3,5,7,32,2,34,34,5])

Если вы также хотите иметь отрицательные элементы в своих списках, вам нужно добавить несколько ifs.

То же самое - в меньших строках

def maxsubseq2(iterable):
    incl = [] # maximal sequence including the previous item
    excl = [] # maximal sequence not including the previous item

    for x in iterable:
        # current max excluding x
        excl_new = incl if sum(incl) > sum(excl) else excl
        # current max including x
        incl = excl + [x]
        excl = excl_new

    return incl if sum(incl) > sum(excl) else excl

То же - устранение sum()

def maxsubseq3(iterable):
    incl = [] # maximal sequence including the previous item
    excl = [] # maximal sequence not including the previous item
    incl_sum, excl_sum = 0, 0
    for x in iterable:
        # current max excluding x
        if incl_sum > excl_sum:
            # swap incl, excl
            incl, excl = excl, incl
            incl_sum, excl_sum = excl_sum, incl_sum
        else:
            # copy excl to incl
            incl_sum = excl_sum #NOTE: assume `x` is immutable
            incl     = excl[:]  #NOTE: O(N) operation
        assert incl is not excl
        # current max including x
        incl.append(x)
        incl_sum += x
    return incl if incl_sum > excl_sum else excl

Хорошо, пусть оптимизирует его...

Версия с общим временем выполнения O (n):

def maxsubseq4(iterable):
    incl = [] # maximal sequence including the previous item
    excl = [] # maximal sequence not including the previous item
    prefix = [] # common prefix of both sequences
    incl_sum, excl_sum = 0, 0
    for x in iterable:
        if incl_sum >= excl_sum:
            # excl <-> incl
            excl, incl = incl, excl
            excl_sum, incl_sum = incl_sum, excl_sum
        else:
            # excl is the best start for both variants
            prefix.extend(excl) # O(n) in total over all iterations
            excl = []
            incl = []
            incl_sum = excl_sum
        incl.append(x)
        incl_sum += x
    best = incl if incl_sum > excl_sum else excl
    return prefix + best # O(n) once

Ответ 2

Ответ Криса терпит неудачу в списке [9,10,9], производя 10 вместо 9 + 9 = 18.

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

Одним из возможных решений могло бы быть рекурсивное решение:

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

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

- MarkusQ

[Изменить] ---

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

Вы можете обернуть функцию выше, чтобы она только вычисляла значение для каждого массива один раз (при первом его вызове), а при последующих вызовах просто возвращал сохраненный результат. Это займет 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) если /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).

Ответ 3

find_max(int t, int n)
{

     if(t>=n)
       return 0;
     int sum =0, max_sum =0;
     for(int i=t; i<n; ++i)
     {
       sum = sum + A[i];
       for(int j=i+2; j<n; ++j)
          sum = sum + find_max(A[j], n);
       if(sum > max_sum)
          max_sum = sum;
     }
     return max_sum;

}

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

Ответ 4

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

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]))

Изменить: Здесь версия, которая возвращает фактическую подпоследовательность, а не только ее сумму. Он растягивает границы моей псевдо-Prolog-C Chimera, поэтому я остановлюсь сейчас.

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

Ответ 5

@MarkusQ answer как Python oneliner (измененный как @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 and sth 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 answer:

(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)))

Ответ 6

Вот ответ, выполненный с использованием динамического программирования с использованием той же базовой концепции, что и MarkusQ. Я просто вычисляю сумму, а не фактическую последовательность, которая может быть произведена простой модификацией этого примера кода. Я удивлен, что никто не упоминал об этом, потому что динамическое программирование выглядит лучше, чем рекурсия + воспоминания!

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;
}

Ответ 7

max (oddIndexSum, evenIndexSum) не работает

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

Ответ 8

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

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

Ответ 9

Чтобы избежать рекурсии, мы можем взять от реверса вперед,

ie) для Array A [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) = max (A [n-1] + maxSum (A, n-3), maxSum (A, n-2)), где в Max (A, n-2) уже получить, и нет необходимости пересчитывать). В других словах вычисляют maxSum (A, n) для всех n, начиная с 1 по n, используя приведенную выше формулу, чтобы избежать перекомпоновки.

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

Ответ 10

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

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, только отменяемое и оптимизированное.

Ответ 11

Edit: Это действительно обман sth, но я не понимал этого, пока не опубликовал его.

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

псевдокод:

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)

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

Ответ 12

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

Ответ 13

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