Love (Skip) thy neighbor

Question

Given a list of n positive numbers, your objective is to select the set of numbers that maximized the sum of selected numbers, given the constraint that we cannot select two numbers that are located adjacent to each other. Describe a linear time algorithm for this problem.

Please provide the Notation, optimality, recurrence, and algorithm.

Answer 1

Notation: S(i) where S(i) is the sum of the largest set up to the i position

Recurrence Relation: S(i) =max{S(i-2) + A[i], S(i-1)}

Optimality: Given the set of numbers {1,3,8,16,2, 3, 10, 40, 22, 35, 64} the above algorithm would find {1,3,9,19, 19, 22, 29, 62, 62, 97, 126}  providing a set of {3, 16, 3, 40, 64} = 126.  

If we assume the maximum number of options (even or odd) is the best answer we would get {1, 8, 2, 10, 22, 64} = 115 or {3, 16, 3, 40, 22, 35} = 119 both of which is suboptimal to the proposed algorithm.

Algorithm:

A[n] = {1,3,8,16,2, 3, 10, 40, 22, 35, 64}
S[n]
s[0] = a[0]
if(a[1] > S[0]) {

    S[1] = a[1]

} else {

    S[1] = s[0]

}

for(int i = 2; i < n; i++) { 

    if(S[i - 1] > S[i-2] + A[i]) { 

        s[i] = s[i-1] 

    } else { 

        S[i] = S[i-2] + A[i] 

    }

Answer 2

Using P(j) represent the maximum sum of the points that can be achieved by first j numbers with no adjacent numbers are selected. 

So the P(j) = max {P(j - 1), P(j - 2) + PV(j)}  This means that when we calculate the sum of the points we choose, the first situation is we select the first (j-1) elements and do not use j-th element;

The second situation is we select (j-2) elements and the j-th element (because we can not select consecutively) and get the maximum of them. 

And  we need to treat a1 and a2 specially because they may not meet the requirements of (j - 2 >=0) .

So the persudo code is : P[1] = PV[1] 

                                    P[2] = max{PV[1], PV[2]}

                                            for j = 3 to n

                                               P[j] = max {P[j -1] , P[j - 2] + PV[j]}             

There is only one simple loop in the algorithm, the time complexity is O(n). 

Answer 3

Using S(j) represent the maximum sum of the points that can be achieved by first j numbers 

S(j) can be defined recursively as follows:

s(j)=max{s(j-1),s(j-2)+pv[j]}

The two arguments in the max function correspond to the cases where we select (j – 1)-th element and  then j-th element, or we select j-th element and  (j – 1)-th element. As if S(j) is optimal, then the sub-solutions S(j-1) and S(j-2) must be optimal as well.

the persudo code is  

S[1] = a[1]

S[2] = max{pv[1], pv[2]} 

for j = 3 to n

    S[j] = max {S[j-1], S[j-2]+pv[j]  

 The time complexity is O(n).