(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.

Divya Biyani

--

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

  1. If the length of arr is 0, return 0.
  2. If the length of arr is 1, return arr[0].
  3. 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.

--

--

Divya Biyani

Software Developer by profession, with a passion of sharing knowledge.