Find Maximum Sum of Non-Adjacent Elements

Title: Find Maximum Sum of Non-Adjacent Elements

In this guide, you’ll learn how to find the maximum sum of non-adjacent elements in an array using Java. This is a classic dynamic programming problem, sometimes called the House Robber problem, and it is a favorite in interviews because the naive approach looks tempting but is wrong.

You’ll see the full algorithm, a step-by-step trace of the recurrence, several worked examples, and the edge cases and follow-up questions interviewers commonly use to probe whether you understand the pattern or just memorized a solution.

Understanding the Problem

Given an array of integers, you need to select a subset of elements so that no two chosen elements sit next to each other in the array, and the sum of the selected elements is as large as possible.

If you pick two elements, there must be at least one unselected element between them in the original array. You are free to skip as many elements as you like, and you may also choose zero elements.

This adjacency rule rules out the simpler strategy of just summing every positive value, because two large adjacent elements cannot both be taken even if that would produce a bigger total.

Approach

1. Handle the trivial cases first: an empty array has a maximum sum of 0, and a single-element array’s answer is that one element.
2. Maintain two running values as you scan the array: include, the best sum of a non-adjacent subset that uses the current element, and exclude, the best sum of a subset that does not use it.
3. Initialize include = nums[0] and exclude = 0 before the loop, since at index 0 there is nothing before it to exclude.
4. For each index i from 1 onward, compute a new include as exclude + nums[i], because taking nums[i] means the previous element must have been skipped.
5. Compute a new exclude as Math.max(include, exclude) using the previous iteration’s values, since skipping nums[i] means you keep whichever running total was already better.
6. Assign both new values back into include and exclude before moving to the next index.
7. After the loop finishes, return Math.max(include, exclude) as the final answer.

Java Program

public class MaximumSumNonAdjacentElements {

    public static int maxSumNonAdjacent(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int include = nums[0];
        int exclude = 0;

        for (int i = 1; i < nums.length; i++) {
            int newInclude = exclude + nums[i];
            int newExclude = Math.max(include, exclude);
            include = newInclude;
            exclude = newExclude;
        }

        return Math.max(include, exclude);
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 5, 10, 7};
        System.out.println("Maximum sum of non-adjacent elements: " + maxSumNonAdjacent(nums));
    }
}

Explanation of the Program

The method maxSumNonAdjacent walks the array once, carrying forward just enough state to decide the best choice at every index.

• The first if handles a null or empty array by returning 0, treating ‘no elements’ as a valid, zero-sum selection.
• The second if handles a single-element array directly, since there is no adjacency constraint to apply with only one value.
• include starts as nums[0] because taking only the first element is the best ‘uses index 0’ answer before any comparisons happen.
• exclude starts at 0 because there is no valid subset yet that skips index 0 and still uses an earlier element.
• Inside the loop, newInclude adds nums[i] onto the previous exclude, enforcing that the element right before i was not chosen.
• newExclude takes the larger of the previous include and exclude, because skipping nums[i] means the best total so far carries over unchanged.
• Both variables update together at the end of each pass so that the next iteration never reads a half-updated state.
• The final Math.max(include, exclude) covers both possibilities: the optimal subset either uses the last element or it does not.

Step-by-Step Trace

Trace the algorithm on nums = {8, 3, 5, 10, 2}, where the expected output is 18 (choosing index 0 and index 3, that is 8 + 10).

At the end of each iteration i, include holds the best non-adjacent sum that must use nums[i], and exclude holds the best non-adjacent sum that does not use nums[i], so Math.max(include, exclude) is always correct so far.

Examples

Example 1: Typical Mixed Array

With nums = {3, 2, 5, 10, 7}, the best non-adjacent subset is indices 0, 2, and 4, giving 3 + 5 + 7 = 15.

int[] nums = {3, 2, 5, 10, 7};
int result = maxSumNonAdjacent(nums);
// result = 15 (3 + 5 + 7, skipping 2 and 10)
System.out.println(result);

Example 2: Array With Negative Numbers

With nums = {5, -1, 5, -1, 5}, the recurrence naturally avoids the negative values because excluding them keeps the running total higher.

int[] nums = {5, -1, 5, -1, 5};
int result = maxSumNonAdjacent(nums);
// result = 15 (5 + 5 + 5, the -1 values are always skipped)
System.out.println(result);

Example 3: Single-Element Array

With only one element, there is nothing to compare against, so the method returns that element directly without entering the loop.

int[] nums = {7};
int result = maxSumNonAdjacent(nums);
// result = 7 (only one element, so it is automatically the answer)
System.out.println(result);

Common Mistakes to Avoid

These are the mistakes candidates actually make on this problem, usually by reaching for a pattern from a different, simpler problem.

• Summing every positive element – this ignores the adjacency rule entirely and overcounts when two large positive values sit next to each other. Track include and exclude per index instead of a single running total.
• Initializing exclude to nums[0] – this makes the base case wrong, since exclude at index 0 should represent ‘nothing chosen yet’, which is 0, not the first element. Start with include = nums[0] and exclude = 0.
• Comparing only two adjacent values at a time – a local, greedy comparison between nums[i] and nums[i - 1] misses better combinations that span farther apart. Use the include and exclude recurrence so every earlier index still influences the current decision.
• Updating include before computing the new exclude – overwriting include first and then using its new value to compute exclude corrupts the recurrence, because exclude must compare against the previous iteration’s values. Compute both newInclude and newExclude first, then assign them together.
• Assuming the array is circular – treating nums[0] and nums[nums.length - 1] as non-adjacent when the problem actually wraps around (as in House Robber II). Confirm whether the array is linear or circular before coding, and run the linear algorithm twice for the circular variant.

Edge Cases to Test

Walk through these inputs before you consider the solution finished; interviewers specifically look for candidates who raise them unprompted.

• Empty array
• Single-element array
• Two-element array
• All negative elements
• All identical elements
• Maximum value at the first or last index
• Alternating large and small values
• Null array reference

Additional Considerations

The algorithm runs in O(n) time, making a single pass over the array and doing constant work at each index.

Space usage is O(1), since only include and exclude are kept in memory rather than a full DP array indexed by position. This is a meaningful improvement over a naive table-based solution when nums is large.

The two-element array case is worth calling out separately: with {a, b}, the elements are always adjacent to each other, so the answer is simply Math.max(a, b), which the recurrence produces automatically without a special case.

Interview Follow-up Questions

Once you have the base solution working, expect an interviewer to push on these variations to see how far your understanding of the recurrence extends.

• What if the array is circular, so the first and last elements count as adjacent? – run the linear recurrence twice, once over nums[0..n-2] and once over nums[1..n-1], and return the larger of the two results.
• What if you also need to report which indices were chosen, not just the total? – record at each step whether include or exclude won, then walk backward from the last index to reconstruct the selection.
• What if elements must be separated by at least two positions instead of one? – the recurrence needs to look two steps back instead of one, so keep a short sliding window of the last two ‘best so far’ values rather than a single pair.
• What if the array arrives as an unbounded stream and can’t be stored? – keep only the include and exclude variables, update them as each element arrives, and report Math.max(include, exclude) at any point; no full array ever needs to be held in memory.

Conclusion

Finding the maximum sum of non-adjacent elements comes down to tracking two running totals, one that uses the current element and one that does not, and letting the better of the two carry forward. Once that recurrence clicks, the problem collapses into a single O(n) pass with O(1) extra space.

Try adapting the program to the circular variant or to reconstruct the chosen indices, both of which reuse the same core idea. You can learn more about array-based problems like this one in the Arrays category: https://dailyjavaconcept.com/category/arrays/