Maximum Non-Adjacent Subsequence Sum

Given an array of integers, determine the maximum sum of a subsequence without choosing adjacent elements in the original array.

Input:

The first line consists of an integer 'T', the number of test cases.
For each test case, the first line contains an integer 'N', the number of elements in the array.
Followed by a line of 'N' space-separated integers, representing the array elements.

Output:

For each test case, output the maximum sum of non-adjacent elements, each result on a new line.

Example:

Input:

2
4
3 2 7 10
3
3 2 5

Output:

13
8

Explanation:

In the first test case, selecting 3 and 10 gives a sum of 13; not selecting adjacent 2. In the second test case, selecting 3 and 5 results in the maximum sum of 8.

Constraints:

1

Question

Maximum Non-Adjacent Subsequence Sum

Given an array of integers, determine the maximum sum of a subsequence without choosing adjacent elements in the original array.

Input:

The first line consists of an integer 'T', the number of test cases.
For each test case, the first line contains an integer 'N', the number of elements in the array.
Followed by a line of 'N' space-separated integers, representing the array elements.

Output:

For each test case, output the maximum sum of non-adjacent elements, each result on a new line.

Example:

Input:

Output:

13
8

Explanation:

In the first test case, selecting 3 and 10 gives a sum of 13; not selecting adjacent 2. In the second test case, selecting 3 and 5 results in the maximum sum of 8.

Constraints:

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

Accepted Answer

Find the maximum sum of a subsequence without choosing adjacent elements in an array.

Use dynamic programming to keep track of the maximum sum at each index, considering whether to include or exclude the current element.
At each index, the maximum sum can be 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 accordingly.
Example: For input [3, 2, 7, 10], the maximum non-adjacent subsequence sum is 13 (3 + 10).

Maximum Non-Adjacent Subsequence Sum

Input:

Output:

Example:

Input:

Output:

Explanation:

Constraints:

American Express Software Developer interview questions & answers

Popular interview questions of Software Developer