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