Code Logo

Max Non-Adjacent Sum

Published at05 Jan 2026
Created by
Array Manipulation Easy 19 views
Like20

This problem asks for the largest sum you can build from an array when you are not allowed to pick two neighboring elements. Once you take a value at one index, the values directly next to it can no longer be used.

That restriction is what makes the problem interesting. A number might look attractive by itself, but taking it may block a better combination later. So the real question is not just whether a single value is large. It is whether taking it leads to a better total than skipping it.

For example, if nums = [1,2,3,1], the best result is 4 by taking 1 and 3. If nums = [2,7,9,3,1], the answer is 12 from 2 + 9 + 1. In nums = [5,1,1,5], taking both end values gives 10, which is better than any choice involving adjacent numbers.

So the task is to decide, for each position, whether it is better to include that value and skip its neighbor or ignore it and keep the best total found so far, then return the maximum total at the end.

Example Input & Output

Example 1
Input
nums = [1, 2, 3, 1]
Output
4
Explanation

Choose 1 (index 0) and 3 (index 2) for a total of 4.

Example 2
Input
nums = [2, 7, 9, 3, 1]
Output
12
Explanation

One optimal choice is 2 (index 0), 9 (index 2), and 1 (index 4) for a total of 12.

Example 3
Input
nums = [5, 1, 1, 5]
Output
10
Explanation

Choose 5 (index 0) and 5 (index 3) for a total of 10.

Algorithm Flow

Recommendation Algorithm Flow for Max Non-Adjacent Sum

Solution Approach

Find the maximum sum of non-adjacent elements in an array (house robber problem). For each element, decide whether to take it or skip it. If taken, add it to the best sum from two positions back. If skipped, take the best sum from one position back. Use rolling variables.

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  var prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);
  for (var i = 2; i < nums.length; i++) {
    var cur = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1; prev1 = cur;
  }
  return prev1;
}

The recurrence considers skipping the current house (keep prev1) or robbing it (prev2 + nums[i]).

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int rob(Object nums) {
        int[] arr = (int[]) nums;
        if (arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0];
        }
        int prev2 = arr[0];
        int prev1 = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            int curr = Math.max(prev1, prev2 + arr[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}