Maximum Sum With No Two Adjacent Elements: DP Approaches Explained

Given an array of positive integers, find the largest possible sum of a subset where no two selected elements sit at consecutive indices. This is LeetCode 198 (House Robber) reframed, and it appears in placement coding rounds across service and product companies.

Problem Statement

• Input: an array arr of n non-negative integers.
• Constraint: if you pick arr[i], you cannot pick arr[i-1] or arr[i+1].
• Output: the maximum sum achievable under that constraint.

Clarification on “adjacent”

“Adjacent” means consecutive indices in the original array, not elements with consecutive values. For arr = [3, 2, 7, 10], elements 3 (index 0) and 7 (index 2) are non-adjacent despite being two apart in value. Elements 7 (index 2) and 10 (index 3) are adjacent because their indices differ by 1.

Approach 1 — Brute-Force Recursion

At each index you have two choices: include the current element (then skip the next) or exclude it (then consider the next). This gives a binary decision tree.

def max_sum_recursive(arr, i):
    if i >= len(arr):
        return 0
    # Include arr[i], skip i+1
    include = arr[i] + max_sum_recursive(arr, i + 2)
    # Exclude arr[i], move to i+1
    exclude = max_sum_recursive(arr, i + 1)
    return max(include, exclude)

# Usage
result = max_sum_recursive([3, 2, 7, 10], 0)  # returns 13

Why this is impractical

The recursion tree has overlapping subproblems. max_sum_recursive(arr, 2) gets called from both the include-path of index 0 and the exclude-path of index 1. Without memoisation, time complexity is O(2^n). For n = 40, that is over a trillion calls.

Approach 2 — Dynamic Programming (Tabulation)

Define dp[i] as the maximum sum considering elements from index 0 to i.

• Base cases: dp[0] = arr[0], dp[1] = max(arr[0], arr[1])
• Recurrence: dp[i] = max(dp[i-1], dp[i-2] + arr[i])

The logic: either we skip index i (best sum is dp[i-1]) or we take index i plus the best sum up to i-2.

def max_sum_dp(arr):
    n = len(arr)
    if n == 0:
        return 0
    if n == 1:
        return arr[0]

    dp = [0] * n
    dp[0] = arr[0]
    dp[1] = max(arr[0], arr[1])

    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])

    return dp[n - 1]

Worked Example 1

• arr = [3, 2, 7, 10]
• dp[0] = 3
• dp[1] = max(3, 2) = 3
• dp[2] = max(dp[1], dp[0] + 7) = max(3, 10) = 10
• dp[3] = max(dp[2], dp[1] + 10) = max(10, 13) = 13
• Answer: 13 (elements at indices 0 and 3, i.e., 3 + 10)

Worked Example 2

• arr = [5, 5, 10, 100, 10, 5]
• dp[0] = 5
• dp[1] = max(5, 5) = 5
• dp[2] = max(5, 5 + 10) = 15
• dp[3] = max(15, 5 + 100) = 105
• dp[4] = max(105, 15 + 10) = 105
• dp[5] = max(105, 105 + 5) = 110
• Answer: 110 (elements at indices 0, 3, and 5, i.e., 5 + 100 + 5)

Complexity

• Time: O(n) — single pass through the array.
• Space: O(n) — the dp array.

Approach 3 — Space-Optimised DP

Since dp[i] depends only on dp[i-1] and dp[i-2], we don’t need the full array. Two variables suffice.

def max_sum_optimised(arr):
    n = len(arr)
    if n == 0:
        return 0
    if n == 1:
        return arr[0]

    prev2 = arr[0]
    prev1 = max(arr[0], arr[1])

    for i in range(2, n):
        current = max(prev1, prev2 + arr[i])
        prev2 = prev1
        prev1 = current

    return prev1

Trace Through Example 1

• arr = [3, 2, 7, 10]
• prev2 = 3, prev1 = max(3, 2) = 3
• i = 2: current = max(3, 3 + 7) = 10, prev2 = 3, prev1 = 10
• i = 3: current = max(10, 3 + 10) = 13, prev2 = 10, prev1 = 13
• Returns 13.

Trace Through Example 2

• arr = [5, 5, 10, 100, 10, 5]
• prev2 = 5, prev1 = max(5, 5) = 5
• i = 2: current = max(5, 5 + 10) = 15, prev2 = 5, prev1 = 15
• i = 3: current = max(15, 5 + 100) = 105, prev2 = 15, prev1 = 105
• i = 4: current = max(105, 15 + 10) = 105, prev2 = 105, prev1 = 105
• i = 5: current = max(105, 105 + 5) = 110, prev2 = 105, prev1 = 110
• Returns 110.

Complexity

• Time: O(n)
• Space: O(1) — only two extra variables regardless of input size.

Complexity Comparison

Approach	Time	Space	Interview notes
Brute-force recursion	O(2^n)	O(n) call stack	Explain to show understanding; never submit as final answer
DP tabulation	O(n)	O(n)	Accepted in most rounds; clear and readable
Space-optimised DP	O(n)	O(1)	Ideal final answer; shows mastery of state compression

Common Mistakes

• Off-by-one in dp initialisation: forgetting to handle dp[1] = max(arr[0], arr[1]) and instead writing dp[1] = arr[1]. This fails when arr[0] > arr[1].
• Confusing “adjacent in array” with “adjacent in value”: the constraint is about index proximity, not value proximity. Students who misread the problem may sort the array first, which destroys the adjacency structure.
• Assuming negatives won’t appear: the standard problem assumes non-negative inputs. If an interviewer introduces negatives, ensure your base case doesn’t force a pick (allow zero as a valid sum, or track whether any element was included). See the GeeksforGeeks discussion for the negative-values variant.
• Forgetting the n == 1 base case: accessing arr[1] on a single-element array crashes the program.

Variations Interviewers Like to Add

Once you have the core DP solution, expect follow-ups. These three variants appear most often in placement rounds.

Circular array — first and last are adjacent

LeetCode 213 (House Robber II) makes the array circular: index 0 and index n-1 are now adjacent. The trick is to run the linear algorithm twice. Once on the slice excluding the last element, once on the slice excluding the first, then return the larger of the two results. Both sub-problems are non-circular and the original recurrence applies unchanged. The decision of which element to exclude is forced by the circular constraint, not chosen during the DP.

Reconstruct which elements were picked

Some interviewers follow up with “now print the elements, not just the sum.” Keep the full dp array rather than the O(1)-space optimisation, then backtrack from dp[n-1]: if dp[i] equals dp[i-1], element i was skipped, move to i-1. Otherwise it was included, add arr[i] to the result and move to i-2. This runs in O(n) extra time on top of the original O(n) DP, and demonstrates that you can recover a full solution path from the optimal-value table.

Binary tree variant (LeetCode 337)

Same constraint, no two adjacent nodes selected, but “adjacency” is parent-child in a binary tree rather than consecutive in an array. The recurrence shifts to post-order traversal: at each node compute an (include, exclude) pair from both children, then return the optimum for the current subtree. The branching structure makes the problem harder to space-optimise, but the include-or-exclude decision logic transfers directly from the array version.

Where This Problem Appears

This problem (or its variants) shows up in campus placement evaluation tests at companies like D.E. Shaw, Amazon, and Goldman Sachs. It tests whether a candidate can recognise overlapping subproblems, write a clean recurrence, and optimise space. If you’re building a DP repertoire for placements, pair this with the 0-1 Knapsack and Longest Increasing Subsequence problems to cover the three most common DP patterns interviewers test. For placement preparation resources covering DP and beyond, the standard references remain Cormen (CLRS) for theory and Karumanchi for interview-style practice.

The rolling-variable optimisation in Approach 3 is a pattern that recurs across DP problems: Fibonacci, climbing stairs, minimum cost path. Once you internalise “only the last two states matter,” you can compress space on any problem whose recurrence looks back a fixed number of steps. TinkerLLM’s interactive coding environment lets you trace through state transitions step-by-step at ₹299, which is useful when a dry trace on paper isn’t clicking.