Maximum Non-Adjacent Sum

Given an array of integers, determine the maximum sum that can be obtained by selecting a subset of elements such that no two chosen elements are adjacent in the original array. Formally, if you denote the array as \(A = [a_0, a_1, \ldots, a_{n-1}]\), you need to select indices \(\{i_1, i_2, \ldots, i_k\}\) with the restriction that \(|i_j - i_{j+1}| \ge 2\) for all valid \(j\), and maximize \(\sum_{j=1}^{k} a_{i_j}\). If the best achievable sum is negative, output 0 instead.

For example, if the input array is [3, 2, 5, 10, 7], one optimal selection is \(3 + 5 + 7 = 15\). Note that you cannot pick 3 and 2 because they are adjacent.

inputFormat

The input is read from stdin and has the following format:

1. An integer \(n\) representing the number of elements in the array.
2. A line containing \(n\) space-separated integers.

You can assume that \(0 \le n \le 10^5\) and each integer fits within the 32-bit signed integer range.

outputFormat

Output a single integer to stdout which is the maximum sum obtainable by selecting a subset of non-adjacent elements. If no valid subset can yield a positive sum, output 0.

5
3 2 5 10 7

15