Algorithm to find the maximum subsequence of an array of positive numbers . Catch : No adjacent elements allowed

Question

For example , given

A = [1,51,3,1,100,199,3], maxSum = 51 + 1 + 199 = 251.

clearly max(oddIndexSum,evenIndexSum) does not work.

The main problem I have is that I can't come up with a selection criterion for an element. A rejection criterion is trivial given a selection criterion.

The standard maximum sub-sequence algorithm doesn't seem to be applicable here. I have tried a dynamic programming approach, but can't come up with that either. The only approach I could come up with was one that used a genetic algorithm.

So how would you approach such a problem? Any help would be appreciated, thanks!

ps: This is not a homework problem, a friend asked me this as we're prepping for interviews.

Answer 1

max(oddIndexSum,evenIndexSum) does not work

For the example you gave, it does - however, if you have something like: A = [1, 51, 3, 2, 41, 23, 20], you can have 51 + 2 + 23 = 76, or you can have 51 + 41 + 20 = 112, which is clearly larger, and avoids adjacent elements as well. Is this what you're looking for?

Answer 2

While you used a bunch of fancy words, isn't this basically just a plain old graph problem of the travelling salesman?

Except in this case you are looking for the most expensive route through the (dense) graph? In this case the vertices are just the numbers themselves, the edges are not directed and have no weight, and all vertices are connected, except to the vertices that had been adjacent to them in the original list?

Answer 3

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

Answer 4

You can build the maximal subsequence step by step if you keep two states:

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

If you also want to have negative elements in your lists, you have to add a few ifs.

Same -- in lesser lines

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

Same -- eliminating 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

Allright, let's optimize it...

Version with total runtime 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

Answer 5

Chris's answer fails on the list [9,10,9], producing 10 instead of 9+9 = 18.

Joe is not quite right. Traveling salesman requires you to visit every city, whereas there's no analog to that here.

One possible solution would be the recursive solution:

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

This has the same big-O as a naive fibonacci function, and should yield to some of the same optimizations (e.g. memoization) if you care about efficiency in addition to simply getting a correct answer.

-- MarkusQ

[Edit] ---

Because some people don't seem to be getting this, I want to explain what I meant by memoization and why it matters.

You could wrap the function above so that it only computed the value for each array once (the first time it was called), and on subsequent calls would simply return the saved result. This would take O(n) space but would return in constant time. That means the whole algorithm would return in O(n) time, better than the exponential time of the less cluttered version above. I was assuming this was well understood.

[Second edit]------------------------------

If we expand the above a bit and tease it apart we get:

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

Which we can unroll into a pseudo basic using only size n arrays of integers and booleans, and the operations of 1) array indexing and indexed array assignment, 2) integer math, including comparison, 3) if/then/else, and 4) one single loop of 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

At the end we can extract the results (in reverse order):

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

Note that what we just did manually is something that a good compiler for a modern language should be able to accomplish with tail recursion, memoization, etc.

I hope that is clear enough.

-- MarkusQ

It's O(n).

Answer 6

A recursive answer in strange Prologesque pseudocode:

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

With appropriate handling of out-of-range indexes.

Edit: This reduces to MarcusQ's nicer answer:

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

Edit: Here's a version that returns the actual subsequence rather than just its sum. It stretches the limits of my ad hoc pseudo-Prolog-C Chimera, so I'll stop now.

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

Answer 7

To avoid recursion, we can take from reverse than forward,

ie) for 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))

To avoid computing of Max(A,n-2), while expanding maxSum(A,n-1), it can be stored and computed. That is why I ask to reverse. ie) maxSum(A,n-1) = max(A[n-1]+ maxSum(A,n-3), maxSum(A,n-2) ) where in Max(A,n-2) is already got, and no need to recalculate ) In otherwords compute maxSum(A,n) for all n starting from 1 to n using above formula to avoid recomputing.

ie) n=2, maxSum = max(A[1]+maxSum(A,0), maxSum(A,1) ) ie) n=3, maxSum = max(A[2]+maxSum(A,2), maxSum(A,2) ) and so on .. and reach last n. this will be o(n).

Answer 8

@MarkusQ's answer as a Python oneliner (modified as @recursive suggested in the comments):

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

Example:

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

It is inefficient, but It might be used to test faster solutions.

Same -- in 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))

Iterative version (O(N) if tail-recursion is available)

It is based on @sth's 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))))

Example:

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

Output:

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

Answer 9

We can use an auxiliary array B[0..n-1], where B[i] is the maximum sum of the elements A[0..i] and C[0..n-1], where C[i] is boolean telling if A[i] is in the maximum sum subsequence:

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

This clearly works in O(n) time and space. Actually, this is the same as MarcusQ's solution, only reversed and optimized.

Answer 10

Edit: This is really a dupe of sth's, but I didn't realize it until after I posted it.

You can do this in constant space and linear time, assuming you don't need to keep track of which items contribute to the final sum.

Pseudocode:

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)

Getting the actual list is an exercise left up to the reader. Or me if you add more comments. But it should be obvious from the algorithm.

Answer 11

MarkusQ's code appears to completely skip over a[2]. I'm not smart enough to figure out where it should figure into the reckoning.

Answer 12

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