Maximum sum of non-adjacent elements

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
448 upvotes
Asked in companies
Expedia GroupOYOOLX Group

Problem statement

You are given an array/list of ‘N’ integers. You are supposed to return the maximum sum of the subsequence with the constraint that no two elements are adjacent in the given array/list.

Note:
A subsequence of an array/list is obtained by deleting some number of elements (can be zero) from the array/list, leaving the remaining elements in their original order.
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array.

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output format:
For each test case, print a single integer that denotes the maximum sum of the non-adjacent elements.

Print the output of each test case in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 500
1 <= N <= 1000
0 <= ARR[i] <= 10^5

Where 'ARR[i]' denotes the 'i-th' element in the array/list.

Time Limit: 1 sec.
Sample Input 1:
2
3
1 2 4
4
2 1 4 9
Sample Output 1:
5
11
Explanation to Sample Output 1:
In test case 1, the sum of 'ARR[0]' & 'ARR[2]' is 5 which is greater than 'ARR[1]' which is 2 so the answer is 5.

In test case 2, the sum of 'ARR[0]' and 'ARR[2]' is 6, the sum of 'ARR[1]' and 'ARR[3]' is 10, and the sum of 'ARR[0]' and 'ARR[3]' is 11. So if we take the sum of 'ARR[0]' and 'ARR[3]', it will give the maximum sum of sequence in which no elements are adjacent in the given array/list.
Sample Input 2:
2
5
1 2 3 5 4
9
1 2 3 1 3 5 8 1 9
Sample Output 2:
8
24
Explanation to Sample Output 2:
In test case 1, out of all the possibilities, if we take the sum of 'ARR[0]', 'ARR[2]' and 'ARR[4]', i.e. 8, it will give the maximum sum of sequence in which no elements are adjacent in the given array/list.

In test case 2, out of all the possibilities, if we take the sum of 'ARR[0]', 'ARR[2]', 'ARR[4]', 'ARR[6]' and 'ARR[8]', i.e. 24 so, it will give the maximum sum of sequence in which no elements are adjacent in the given array/list.
Hint

Explore all the possible subsequences with given constraints.

Approaches (3)
Recursive Approach (top down)

We are going to explore all the possibilities of subsequences in which there will be no two elements that are adjacent to one another in the given array/list. So if we take the current element, let’s say ‘CURR’ then we are not allowed to take the element adjacent to ‘CURR’. So for that, we will call a recursive function one step forward to the ‘CURR’. 

 

The Steps are as follows:

 

  1. If the given array/list is empty, then return 0 because we don’t have any value to make the subsequence.
  2. Else, You have two options for every index of the given array/list. Let’s say we are at ‘INDEX’: Include the current element 'ARR[‘INDEX’]' for our subsequence or, Exclude the current element from our subsequence.
  3. If an option 'a' is selected it means you can't take ‘ARR[‘INDEX’ - 1]’ element but can safely proceed to the one before the previous, i.e. ‘ARR[‘INDEX’ - 2]' and get all cumulative sums that follow.
  4. If an option 'b' is selected, then we are allowed to take all the possible elements into subsequence till ‘INDEX’ - 1 from the given array/list.
  5. So we will recursively call on option ‘a’ and option ‘b’ and store it in “optionA” and “optionB” respectively. Thus, A recurrence relation of the above steps will be:
maximumNonAdjacentSum(index) = max( maximumNonAdjacentSum(index-2) + ARR[index], maximumNonAdjacentSum(index-1))
Time Complexity

O(2^N ), Where ‘N’ is the number of elements in the given array/list.

 

Since for each element in the given array/list, we have two choices, either we can include it into our subsequence or not. So for the ‘N’ number, there will be 2 ^ N possible choices. So, the overall time complexity will be O(2 ^ N).

Space Complexity

O(N), Where ‘N’ is the number of elements in the given array/list.

 

Since we are using the recursion for exploring all the possible combinations, so in the worst case when we keep excluding the elements from our subsequence then there will be the depth of the recursion tree will be O(N). So, overall space complexity will be O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Maximum sum of non-adjacent elements
Full screen
Console