Maximum sum of non-adjacent elements

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.

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.

Approach 1

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

Try Problem

Approach 2

In the first approach, there was higher time complexity, so how to reduce that?

The cause of increased time complexity was that we were solving redundant subproblems repeatedly, so in order to reduce these redundant function calls, we can store the previous results.

When we are at the current element in the given array/list, we have two options that either we can include the current element or exclude it from our subsequence, If we take the current element, let’s say ‘CURR’ then we are not allowed to take the element adjacent to the ‘CURR’.

Hence we will use a bottom-up approach to solve this question.

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.
While exploring all the possibilities, we can reduce our function calls by storing the previous results in an array, and that results in the use of Dynamic Programming.
We create an array/list (say ‘DP’) for dynamic programming, so for every element in the given array/list we are storing the result at every ‘INDEX’ of the ‘DP’.
Consider two options to either include or exclude the ‘CURR’ element, i.e. ‘ARR[INDEX]' for our subsequence, and we have two options:

Including the ‘CURR’ element, optionA = ‘DP[INDEX - 2]’ + ‘ARR[INDEX]’.
Excluding the ‘CURR’ element, optionB = 'DP[INDEX - 1]'.

So dynamic programming relation comes out to be:

dp[index] = max( optionA, optionB)

Try Problem

Approach 3

Here we are applying a bottom approach (Dynamic Programming) as in the previous one, but now we are looking for reducing space complexity to O(1).

If we try to notice closely, we realise that at every index we only need the results of the previous two positions, i.e. for ‘INDEX' - 2 and ‘INDEX’ - 1. Hence we do not need to store the results in an array/list, and rather we can store it into the two variables.

The steps are as follows:

We assign two variables ‘prevFirst' and ‘prevSecond’, Where ‘prevFirst is the cumulative sum till (’INDEX' - 1)th elements and ‘prevSecond’ is the cumulative sum till ('INDEX' - 2)th elements.
Consider two options to either include or exclude the ‘CURR’ element, i.e. ‘ARR[INDEX]’ in our subsequence, and we have two options:
Including the ‘CURR’ element, optionA = ‘prevSecond’ + ‘ARR[INDEX]’
Excluding the ‘CURR’ element, optionB = ‘prevFirst’.
Return max( optionA, optionB).

Try Problem