☕ DSA Java Articles

Topics › Dynamic Programming › 1D DP

Maximum sum of non adjacent elements

Medium TUF ID 291 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an array nums of non-negative integers, choose some of its elements so that no two chosen elements sit at adjacent indices, and maximise their sum. Choosing nothing is allowed and gives 0.

This is the same problem as LeetCode 198 “House Robber”: houses in a row hold nums[i] money, and robbing two neighbouring houses triggers the alarm.

Constraints: LeetCode allows n ≤ 100 and values up to 400, but other versions allow far larger inputs (for example 10^5 elements of up to 10^5 each). There the total can reach about 5 × 10^9, which overflows int, so the methods return long.

Example 1

nums = [2, 1, 4, 9]
answer = 11         // 2 + 9 (indices 0 and 3)

Example 2

nums = [1, 2, 4]
answer = 5          // 1 + 4; taking 2 would block both neighbours

Why the obvious shortcuts fail

Two shortcuts come to mind, and both are wrong:

Every element is either taken or not, and each decision constrains its neighbours. That is the take / not-take pattern from subsequence recursion, with one extra rule, and DP makes it fast.

Approach 1: Recursion (pick / not pick)

Intuition. Let f(i) be the best sum using only nums[0..i]. Look at the last element, nums[i]:

Every valid selection falls into exactly one of these two cases, so

f(i) = max( nums[i] + f(i - 2), f(i - 1) ),     f(negative) = 0

The answer is f(n - 1). A single base case f(i < 0) = 0 covers everything: f(0) becomes max(nums[0] + 0, 0) = nums[0].

Algorithm.

  1. If i < 0, return 0.
  2. pick = nums[i] + f(i - 2), skip = f(i - 1).
  3. Return max(pick, skip).
static long recursive(int[] nums) {
    return solve(nums.length - 1, nums);
}

static long solve(int i, int[] nums) {
    if (i < 0) return 0;                                    // no elements left
    long pick = nums[i] + solve(i - 2, nums);               // take nums[i], so nums[i - 1] is off limits
    long skip = solve(i - 1, nums);                         // leave nums[i]
    return Math.max(pick, skip);
}

Complexity. Time O(2^n): two branches per call and heavy recomputation. Space O(n) for the recursion depth.

Approach 2: Memoization

Intuition. The recursion only ever asks about prefixes nums[0..i], so there are n states. Remember each answer.

Algorithm.

  1. Create dp of size n filled with -1. Sums of non-negative numbers are never negative, so -1 safely means “not computed”.
  2. In the helper, return dp[i] when it is filled; otherwise compute pick and skip, store the maximum, and return it.
static long memoization(int[] nums) {
    long[] dp = new long[nums.length];
    Arrays.fill(dp, -1);                                    // -1 = not computed (real sums are >= 0)
    return memo(nums.length - 1, nums, dp);
}

static long memo(int i, int[] nums, long[] dp) {
    if (i < 0) return 0;
    if (dp[i] != -1) return dp[i];
    long pick = nums[i] + memo(i - 2, nums, dp);
    long skip = memo(i - 1, nums, dp);
    return dp[i] = Math.max(pick, skip);
}

Complexity. Time O(n), space O(n) for the table plus O(n) stack. At n = 10^5 the stack is too deep for Java’s defaults.

Approach 3: Tabulation

Intuition. dp[i] needs dp[i - 1] and dp[i - 2], so fill left to right. Treat out-of-range indices as 0, exactly like the recursion’s base case.

Algorithm.

  1. For i from 0 to n - 1: pick = nums[i] + (i ≥ 2 ? dp[i - 2] : 0), skip = (i ≥ 1 ? dp[i - 1] : 0), dp[i] = max(pick, skip).
  2. Return dp[n - 1], or 0 for an empty array.
static long tabulation(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    long[] dp = new long[n];
    for (int i = 0; i < n; i++) {
        long pick = nums[i] + (i >= 2 ? dp[i - 2] : 0);
        long skip = i >= 1 ? dp[i - 1] : 0;
        dp[i] = Math.max(pick, skip);
    }
    return dp[n - 1];
}

Dry run on nums = [2, 1, 4, 9]:

i nums[i] pick skip dp[i]
0 2 2 + 0 = 2 0 2
1 1 1 + 0 = 1 2 2
2 4 4 + 2 = 6 2 6
3 9 9 + 2 = 11 6 11

At i = 3, picking 9 combines with dp[1] = 2 (the best of [2, 1]), not with the 6 that used index 2.

Complexity. Time O(n), space O(n).

Approach 4: Space optimized

Intuition. Only the last two table cells are ever read. Keep prev = dp[i - 1] and prev2 = dp[i - 2], both starting at 0 (the values for “before the array”).

Algorithm.

  1. prev2 = prev = 0.
  2. For each x in nums: cur = max(x + prev2, prev), then prev2 = prev, prev = cur.
  3. Return prev.
static long spaceOptimized(int[] nums) {
    long prev2 = 0, prev = 0;                               // dp[i - 2] and dp[i - 1]
    for (int x : nums) {
        long cur = Math.max(x + prev2, prev);
        prev2 = prev;
        prev = cur;
    }
    return prev;
}

Complexity. Time O(n), space O(1). This four-line loop is the answer most interviewers expect, but derive it from the recursion so you can explain it.

Edge cases and pitfalls