c programming puzzle

Question

Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

I tried it using all possible allowed sums and then finding the maximum (the brute force approach) but is there any better method. Eg for [3 2 7 10] I sum 3,7 and 2,10 and take maximum.

---

More examples:

• [3, 2, 7, 1]: return 10
• [6, 2, 1, 4]: return 10
• [8, 9, 5, 1]: return 13
• [29, 77, 16]: return 77
• [29, 44, 16]: return 45

Answer 1

This problem can be solved by dynamic programming.

Let's say we have an array of integers:

i[1], i[2], i[3], ..., i[n], i[n+1], i[n+2]

We partition the array into two parts: the first part containing first n integers, and the second part is the last two integers:

{i[1], i[2], i[3], ..., i[n]}, {i[n+1], i[n+2]}

Let's denote M_SUM(n) as the max sum of the first n integers per your requirement.

There will be two cases:

1. if i[n] is not counted into M_SUM(n), then M_SUM(n+2) = M_SUM(n) + MAX(i[n+1], i[n+2])
2. if i[n] is counted into M_SUM(n), then M_SUM(n+2) = M_SUM(n) + i[n+2]

then, M_SUM(n+2), the value we are seeking for, will be the larger value of the above two.

Then we can have a very naive pseudocode as below:

function M_SUM(n)
   return MAX(M_SUM(n, true), M_SUM(n, false))

function M_SUM(n, flag)
   if n == 0 then return 0
   else if n == 1
      return flag ? i[0] : 0
   } else {
      if flag then
         return MAX(
                M_SUM(n-2, true) + i[n-1], 
                M_SUM(n-2, false) + MAX(i[n-1],i[n-2]))
      else
         return MAX(M_SUM(n-2, false) + i[n-2], M_SUM(n-2, true))
   }

"flag" means "allow using the last integer"

This algorithm has an exponential time complexity.

Dynamical programming techniques can be employed to eliminate the unnecessary recomputation of M_SUM.

Storing each M_SUM(n, flag) into a n*2 matrix. In the recursion part, if such a value does not present in the matrix, compute it. Otherwise, just fetch the value from the matrix. This will reduce the time complexity into linear.

The algorithm will have O(n) time complexity, and O(n) space complexity.