Code Logo

Max Non-Adjacent Sum

Published at05 Jan 2026
Created by
Easy 3 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
Recommendation Algorithm Flow for Max Non-Adjacent Sum

Solution Approach

A good way to solve this problem is with dynamic programming using two running totals. At each number, we choose between two options: skip the current value and keep the best total so far, or take the current value and add it to the best total from two positions back.

This works because the restriction only cares about adjacency. If we take nums[i], then the best total we can combine with it is the best answer up to i - 2. If we skip nums[i], then the answer stays whatever was best up to i - 1.

We can store those two states in two variables:

let prevTwo = 0;
let prevOne = 0;

Here, prevTwo means the best total up to two positions ago, and prevOne means the best total up to the previous position.

Then we process each number and build the new best answer:

for (const num of nums) {
  const current = Math.max(prevOne, prevTwo + num);
  prevTwo = prevOne;
  prevOne = current;
}

prevOne handles the skip case, and prevTwo + num handles the take case. Taking the larger of the two gives the best answer up to the current index.

After the loop, prevOne is the maximum sum with no adjacent selections:

return prevOne;

This runs in O(n) time and uses O(1) extra space.

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;
    }
}