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

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

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.

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.

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

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