 New update is available. Click here to update.

# Maximum sum of non-adjacent elements

Posted: 7 Nov, 2020
Difficulty: Moderate

## 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.
``````