Last Updated: 10 May, 2022

Max Non Adjacent sum

Easy

Asked in companies

Solve now

Problem statement

You are given an array ‘ARR’ of integer elements. You have to find the maximum sum of the subset of elements in the array such that no two elements in the subset are adjacent to each other.

Note: A subset of array ‘ARR’ is a tuple that can be obtained from ‘ARR’ by removing some (possibly all) elements from it, without changing the order of the remaining elements.

EXAMPLE:

Input: 
'N' = 5
‘ARR’ = [1, 2, 3, 4, 5]

Output: 9

The optimal subset would be [1, 3, 5], in which no two elements are adjacent to each other and the sum of the subset is 9. We cannot make the sum greater than 9.

Input Format :

The first line will contain the integer 'T', the number of test cases. For each test case

In the first line of each test case, an integer ‘N’ denotes the length of the array ‘ARR’.
The second line of each test case contains ‘N’ integers denoting the elements of array ‘ARR’.

Output format :

For each test case, print the maximum sum of the subset.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
4 <= 'N' <= 10^5
1 <= ‘ARR[i]’ <= 10^5

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

We will try dynamic programming, where the ith state will denote the answer up to state ‘i’.
If we have calculated the answer up to the ‘i-1th’ state, then to calculate the answer for the ith state we only care about the ‘i-2’ and '‘i-3’ state as all the previous state answer is already considered in these two states.
At the end take the maximum of all states.

Algorithm :

Create a ‘DP’ array and initialize it with ‘ARR’ elements.
Do a for loop from i = 2 to ‘N-1’ (0 indexed)
- Assign ‘DP[i]’ with maximum of ‘DP[i-2] + ARR[i]’ or ‘DP[i-3] + ARR[i]’.
Create a variable ‘RES’ to store the maximum sum.
Store the maximum of ‘DP’ in ‘RES’
Return ‘RES’

Solve now