Finding the maximum weight subsequence of an array of positive integers?

Question

I'm tring to find the maximum weight subsequence of an array of positive integers - the catch is that no adjacent members are allowed in the final subsequence.

The exact same question was asked here, and a recursive solution was given by MarkusQ thus:

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

He provides an explanation, but can anyone help me understand how he has expanded the function? Specifically what does he mean by

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

Why does he expand f[] to [],0? Also how does his solution take into consideration non-adjacent members?

I have some C++ code that is based on this algorithm, which I can post if anyone wants to see it, but I just can't for the life of me fathom why it works.

==========For anyone who's interested - the C++ code ==============

I should add, that the array of integers is to be treated as a circular list, so any sequence containing the first element cannot contain the last.

int memo[55][55];

int solve(int s, int e)
{
    if( s>e ) return 0;
    int &ret=memo[s][e];
    if(ret!=-1)
    {
        return ret;
    }
    ret=max(solve(s+1,e), solve(s+2,e)+a[s]);
    return ret;
}

class Sequence
{
    public:
    int maxSequence(vector <int> s)
    {
            memset(memo,-1);
            int n = s.size();
            for(int i=0; i<n; i++)
                a[i]=s[i];
            return max(solve(0,n-2),solve(1,n-1));
        }
};

Answer 1

But what do you NOT understand? It seems quite clear for me:

• we will build the maximal subsequence for every prefix of our given sequence
• to calculate the maximal subsequence for prefix of length i, we consider two possibilities: Either the last element is, or isn't in the maximal subsequence (clearly there are no other possibilities).
• if it is there, we consider the value of the last element, plus the value of maximal subsequence of the prefix two elements shorter (because in this case, we know the last element cannot be present in the maximal subsequence because of the adjacent elements rule)
• if it isn't we take the value of maximal sum of prefix one element shorter (if the last element of the prefix is not in the maximal subsequence, the maximal subsequence has to be equal for this and the previous prefix)
• we compare and take the maximum of the two

Plus: you need to remember actual subsequences; you need to avoid superfluous function invocations, hence the memoization.

Why does he expand f[] to [],0?

Because the first from the pair in return value means current maximal subsequence, and the second is its value. Maximal subsequence of an empty sequence is empty and has value zero.

Answer 2

I don't really understand that pseudocode, so post the C++ code if this isn't helpful and I'll try to improve it.

I'm tring to find the maximum weight subsequence of an array of positive integers - the catch is that no adjacent members are allowed in the final subsequence.

Let a be your array of positive ints. Let f[i] = value of the maximum weight subsequence of the sequence a[0..i].

We have:

f[0] = a[0] because if there's only one element, we have to take it.
f[1] = max(a[0], a[1]) because you have the no adjacent elements restriction, so if you have two elements, you can only take one of them. It makes sense to take the largest one.

Now, generally you have:

f[i > 1] = max(
           f[i - 2] + a[i] <= add a[i] to the largest subsequence of the sequence a[0..i - 2]. We cannot take a[0..i - 1] because otherwise we risk adding an adjacent element.
           f[i - 1] <= don't add the current element to the maximum of a[0..i - 2], instead take the maximum of a[0..i - 1], to which we cannot add a[i].
              )

I think this way is easier to understand than what you have there. The approaches are equivalent, I just find this clearer for this particular problem, since recursion makes things harder in this case and the pseudocode could be clearer either way.