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)