Maximum Sum of Non-Adjacent Elements

Given an array/list of ‘N’ integers, your task is to return the maximum sum of the subsequence where no two elements are adjacent in the given array/list.

Example:

Input:

T = 1
N = 5
array = [3, 2, 7, 10, 12]

Output:

22

Explanation:

The maximum sum can be obtained by choosing the subsequence [3, 10, 12], which results in a sum of 22. No two chosen elements are adjacent.

Input:

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:

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.

Constraints:

• 1 <= T <= 500
• 1 <= N <= 1000
• 0 <= ARR[i] <= 10⁵
• Time Limit: 1 sec.

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. You do not need to print anything; it has already been taken care of. Just implement the given function.