Max Subset Sum No Adjacent

Tags

Max Subset Sum No Adjacent

Category

Dynamic Programming

Difficulty

Medium

Problem Statement

Given an array of positive integers, find the maximum sum of a subset of the array such that no two elements in the subset are adjacent in the original array. If the array is empty, the maximum sum is 0.

Intuition

At each position, we have two choices: include the current element (and skip the previous one) or exclude the current element (and carry forward the best sum so far). This is a classic DP problem where the state at each position depends on the two previous positions. We build up the solution by considering one element at a time.

Approach

  1. Handle base cases: empty array returns 0; single-element array returns that element.
  2. Initialize: prevPrev = array[0], prev = max(array[0], array[1]).
  3. For each element from index 2 onward:
    • current = max(prev, prevPrev + array[i]) — either skip the current element (take prev) or include it (add it to prevPrev).
    • Shift the window: prevPrev = prev, prev = current.
  4. Return prev.

Pseudocode

function maxSubsetSumNoAdjacent(array):
    if length(array) == 0: return 0
    if length(array) == 1: return array[0]

    prevPrev = array[0]
    prev = max(array[0], array[1])

    for i from 2 to length(array) - 1:
        current = max(prev, prevPrev + array[i])
        prevPrev = prev
        prev = current

    return prev

Time & Space Complexity

  • Time: O(n) where n is the length of the array. Single pass through the array.
  • Space: O(1) — only two variables track the state.

Key Insights

  • This is equivalent to the "House Robber" problem: maximize the loot without robbing two adjacent houses.
  • The recurrence relation is: dp[i] = max(dp[i-1], dp[i-2] + array[i]).
  • We only need the last two DP values, so we can optimize from O(n) space to O(1).
  • Including an element means we must skip the immediately preceding element, but not necessarily the one before that.

Edge Cases

  • Empty array: return 0.
  • Single-element array: return that element.
  • Two-element array: return the maximum of the two.
  • All elements are the same: pick every other element.
  • Array where the optimal solution skips more than one element in a row.

Linked mentions