# (Daily Coding Problem: February 24th, 2020) Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be `0`

or negative.

Hey Guys, Welcome Back! This blog is in continuation with our series of solving a question a day, thanks to **daily coding problem****.**

**Question:- **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, `

1. [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5.

2. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

**Solution:-**

After reading the question, the first thing that came in my mind is **DP**(Dynamic Programming). As scary as these 2 letter sound together, I really like solving DP questions and figuring the solution’s time and space complexity.

**First Approach:-**

The first solution that came to my mind was to create an array named **sum **of the same length of the input arr.

Compute the value of each sum such that sum[i] contains the maximum sum possible from arr[i] to arr[n-1] by choosing only non-adjacent arrays.

So, with the basic idea of starting from the last element,

I came with 3 base case scenarios:-

- If the length of arr is
**0**, return**0.** - If the length of arr is 1, return arr[0].
- If the length of arr is 2, return max(arr[0], arr[1]).

Now, for further backtracking, the logic that I thought was:-

sum[i] = max(arr[i] + sum[i+2], sum[i+1]);// arr[i] + sum[i+2] -> if the element is included itself, the next element cannot be included, hence the sum of next to next element is added// sum[i+1] -> there is also a possibility to not select this element, and use the sum of the adjacent element.

Below is the code implementation in java for the problem based on this approach -

**Time Complexity:- **O(n)**Space Complexity:- **O(n)

**Second Approach:-**

After solving the question through the first approach, I realized that I do not need to store the max sum of non-consecutive numbers for all the elements. I need to know only about the i+1 and i+2 sum information for calculating the max sum of the **ith **position.

Hence, I came up with the logic of only saving 2 sums at a time, and finding the new one and replacing it with the following logic.

`new_sum = max(arr[i] + second, first);`

second = first

first = new_sum

Below is the code implementation in java for the problem based on this approach -

**Time Complexity:- **O(n)**Space Complexity:- **O(1)

That’s all from my side, thank you so much for reading the blog. I will be continuing this series and will keep on discussing everyday problems. For any further discussions, please feel free to reach out to me at *divyabiyani26@gmail.com.*