Maximum Non-Adjacent Sum

You are given an array of integers representing points. Your task is to compute the maximum sum obtainable by selecting a subset of non-adjacent elements. Formally, given an array \(a_1, a_2, \dots, a_n\), you need to choose a subset of indices \(P\) such that no two consecutive indices are chosen, and maximize the sum \(\sum_{i \in P} a_i\). This problem is a classic application of dynamic programming and can be solved in \(O(n)\) time.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(n\) indicating the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

For each test case, output a single integer — the maximum sum of non-adjacent elements in the array. Each answer should be printed on a new line.

2
5
3 2 5 10 7
3
1 2 3

15
4