Around the block party planning

Question

Consider a row of n houses represented as an array: A[1..n], where the phrase "next door neighbor" having its natural meaning. Each resident is assigned a "fun factor" F[1..n], which represents how much fun they bring to a party. Your goal is to maximize the fun of a party that you are arranging, but with the constraint that you cannot select three consecutive neighbors. (So for example, if you invite the A[5] and A[6] family, you cannot invite the A[4] or A[7] families.) Give an efficient algorithm to select the guest list.

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

Answer 1

Notation:

dp[i] to represent the max result until ith element 

Base Cases:
dp[1]=A[1]
dp[2]=A[1]+A[2]
 

Recurrence?

dp[i]=???

Algorithm:

for(i=3; i<=n; i++)

Calculate dp[i] as per recurrence relation above.

Final Solution

dp[n]

Time Complexity

T(n)=O(n)

Answer 2

Notation:

dp[i] to represent the max result until ith element 

Base Cases:
dp[1]=A[1]
dp[2]=A[1]+A[2]

dp[3]=max(A[1]+A[2],A[1]+A[3], A[2]+A[3])  // Either Max of 1 and 2 or 2 and 3 or 1 and 3 since 1, 2 and 3 cannot be adjacent

Recurrence:

dp[i]=max(dp[i-1], dp[i-2] + a[i] , dp[i-3] +a[i] + a[i-1])

We have three case,
Case 1: We do not select a[i], then dp[i] = dp[i-1]
Case 2: We do not select a[i-1], then dp[i] = dp[i-2] + a[i]
Case 3: We do not select a[i-2]. then dp[i] = dp[i-3] + a[i-1] + a[i]

Thus dp[i] = Max(all three cases)

Algorithm:
 

for(i=3; i<=n; i++)

{

dp[i]=max(dp[i-1], dp[i-2] + a[i] , dp[i-3] +a[i] + a[i-1]);

}

return dp[n];

Time Complexity:

Since single loop runs from 3 to n, the time complexity is O(n)

 

Answer 3

You must traverse, so it is impossible to be better than O(n)