Max Non Adjacent sum

Easy
0/40
Average time to solve is 19m
profile
Contributed by
1 upvote
Asked in companies
WalmartBYJUS

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1
10
4
2 1 1 2
Sample Output 1 :
10
4
Explanation Of Sample Input 1 :
In the first test case, the optimal subset is [10] with the sum ‘10’.
Hence the answer is ‘10’.

In the second test case, the optimal subset is [2, 2] with no adjacent elements and sum ‘4’.
Hence the answer is ‘4’.
Sample Input 2 :
2
4
4 3 7 6
4
3 7 5 1
Sample Output 2 :
11
8
Hint

Try Dynamic programming.

Approaches (1)
Dynamic Programming

Approach: 
 

  1. We will try dynamic programming, where the ith state will denote the answer up to state ‘i’.
  2. 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.
  3. 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’
Time Complexity

O(N), Where ‘N’ is the length of the array ‘ARR’.

Calculating the answer for ‘N’ states takes ~N time, the time complexity will be O(N).

Space Complexity

O(N), Where ‘N’ is the length of the array ‘ARR’.


Creating the ‘DP’ array takes ~N space, Hence the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Max Non Adjacent sum
Full screen
Console