[Daily Coding] the largest sum of non-adjacent numbers

Problem

Good morning! Here's your coding interview problem for today.

This problem was asked by Airbnb.

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?

Code

i	0	1	2	3	4	5	6	7	...	n-3	n-2	n-1
nums	5	3	4	1	6	7	4	7	...	1	6	9
sum	sum[0]	sum[1]	sum[2]	sum[3]	sum[4]	sum[5]	sum[6]	sum[7]	...	sum[n-3]	sum[n-2]	sum[n-1]
sum	max(0, sum[0])=5	max(sum[0], arr[1]) = 5	max(sum[2 - 1], arr[2] + sum[0]) = 9	max(sum[3 - 1], arr[3] + sum[3 -2] = )	0	0	0	0	...	0	0	max(sum(n - 1 - 1), arr[n - 1] + arr[n - 1 - 2]) =

It is dP problem!
If we know max sum of non-adjecent [0 - i]
=> max sum [0 - i + 1] is
either
sum [0 - i] (when it is better to pick arr[i] than arr[i + 1])
or
sum [0 - i - 2] + arr[i]. (when it is better to pick arr[i + 1] than arr[i])

    
    // case 1: O(N) space complexity
    int solutionON(int[] arr) {
    	int len = arr.length;
        
        if (len == 0) return 0;
        if (len == 1) return arr[0];
        
    	int[] sum = new int[len];
        sum[0] = Math.max(0, arr[0]);
        sum[1] = Math.max(sum[1 - 0], arr[1]);
        
        for (int i = 2; i < len; i++) { 
        	sum[i] = Math.max(sum[i - 1], arr[i] + sum[i - 2]);
        }
        
        return sum[len - 1];
        
    }
    
    // do we need to store each sum[i]? No! cuz we need last element
    	int solutionO1(int[] arr) {
        	int first = 0;
            int second = 0;
            
            // first second i ...
        	// first + i or second
        	// at 0, first + arr[0], second? arr[0] == sum[0]
        	// at 1, first + arr[1], second(newSum)?
            for (int i = 0; i < arr.length; i++) {
            	int newSum = Math.max(second, first + arr[i]);
                first = second;
                second = newSum;
            }
            
            return second;
        }

complexity

time: O(N) ->
space: O(N) -> O(1)