Given a list of integers, write a function that returns the largest sum of non-adjacent numbers? Numbers can be 0 or negative 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?


class DailyCodingProblem9 {

    public static void main(String args[]) {

        int arr[] = { 2, 4, 6, 2, 5, 13 };
        int res = solution(arr);
        System.out.println(res);

        int arr1[] = { 1, 0, 3, 9, 2, 14 };
        res = solution(arr1);
        System.out.println(res);
    }

    static int solution(int[] arr) {
        int n = arr.length;
        int[] maxArr = new int[n];
        int max = 0;
        for (int i = n - 1; i &gt; 0; i--) {
            maxArr[i] = findLargestSum(arr, i, n, maxArr);
            max = Math.max(max, maxArr[i]);
        }
        return max;

    }

    static int findLargestSum(int[] arr, int i, int n, int[] max) {
        System.out.println(i);
        if (max[i] != 0) {
            return max[i];
        }
        if (i == 0 || i == 1) {
            return arr[i];
        }
        if (i - 2 == 0) {
            return arr[i] + findLargestSum(arr, i - 2, n, max);
        }
        return arr[i] + Integer.max(findLargestSum(arr, i - 2, n, max), findLargestSum(arr, i - 3, n, max));

    }

}


How do I solve it in constant space? I found an answer here, but could not understand the logic.
What you implemented is the recursive solution:

sum(k)
  | k &lt; 0 = 0
  | otherwise = max( sum(k-1), sum(k-2) + arr[k] )


You can also implement it iteratively using an O(n) extra space:

sum = int[n]
sum[0] = max(      0, arr[0] )
sum[1] = max( sum[0], arr[1] )
for (int k = 2; k &lt; n; k++)
{
    sum[k] = max( sum[k-1], sum[k-2] + arr[k] )
}


You may notice that nothing but the two rightmost values will ever be used in the next iteration. We can get rid of the array entirely and store only those values instead, which leads to O(1) space usage.

s2 = max(  0, arr[0] )
s1 = max( s2, arr[1] )
for (int k = 2; k &lt; n; k++)
{
    s0 = max( s1, s2 + arr[k] )
    s2 = s1
    s1 = s0
}