# Apex Coding Interview Challenge #9

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Follow-up: Can you do this in O(N) time and constant space?

**Solution**

public Integer sumLargestNonAdjacentNumbers(List<Integer> lstNumbers){ Integer exclusive = 0; Integer inclusive = lstNumbers.get(0); for (Integer i = 1; i < lstNumbers.size(); i++) { Integer temp = inclusive; inclusive = Math.max(exclusive + lstNumbers.get(i), inclusive); exclusive = temp; } return inclusive; }

**Testing**

System.debug(sumLargestNonAdjacentNumbers(new List<Integer>{5, 1, 1, 5})); //10 System.debug(sumLargestNonAdjacentNumbers(new List<Integer>{2, 4, 6, 2, 5})); //13

**Complexity Analysis**

Time complexity: O(n)

Space complexity: O(1)