Maximum Non-Adjacent Subsequence Sum

Given an array of integers, determine the maximum sum obtainable by selecting a subsequence of non-adjacent elements.

Formally, let \(a = [a_1, a_2, \dots, a_n]\). You need to choose a subset \(S\) of indices such that for any two consecutive indices \(i\) and \(j\) in \(S\), \(|i - j| \ge 2\). The objective is to maximize the sum \(\sum_{i \in S} a_i\). Note that if all numbers are negative, the answer is 0 as you can choose an empty subsequence.

Constraints:

• The first input line contains an integer \(n\) (\(n \ge 0\)).
• If \(n > 0\), the second line contains \(n\) space-separated integers.

Your solution should read input from stdin and write the result to stdout.

inputFormat

The first line contains a single integer \(n\), representing the number of elements in the array. If \(n > 0\), the second line contains \(n\) space-separated integers. If \(n = 0\), there will be no second line.

outputFormat

Output a single integer representing the maximum sum of a subsequence with no two adjacent elements.

5
3 2 5 10 7

15