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

Question

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:

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.

Accepted Answer

Find the maximum sum of non-adjacent elements in an array.

Use dynamic programming to keep track of the maximum sum at each index, considering whether to include the current element or skip it.
At each index, the maximum sum is either the sum of the current element and the element two positions back, or the sum at the previous index.
Iterate through the array and update the maximum sum at each index accordingly.
Return the maximum sum obtained at the last index as the final result.