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

victor·2021년 2월 2일
0

## 알고리즘

목록 보기
21/63

### 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

i01234567...n-3n-2n-1
nums53416747...169
sumsum[0]sum[1]sum[2]sum[3]sum[4]sum[5]sum[6]sum[7]...sum[n-3]sum[n-2]sum[n-1]
summax(0, sum[0])=5max(sum[0], arr[1]) = 5max(sum[2 - 1], arr[2] + sum[0]) = 9max(sum[3 - 1], arr[3] + sum[3 -2] = )0000...00max(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)

캬-!