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.

How would you approach this?

Answer 1

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 2

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