Maximum sum of non-adjacent elements
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.
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.
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.
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.
You do not need to print anything; it has already been taken care of. Just implement the given function.
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.
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:
- If the given array/list is empty, then return 0 because we don’t have any value to make the subsequence.
- 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.
- 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.
- 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.
- 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))