Maximum Sum of Non-Adjacent Elements

You are given an array of integers. Your task is to compute the maximum sum of a subset of these integers such that no two selected elements are adjacent in the array.

Formally, let the array be \(a_1, a_2, \dots, a_n\). You need to choose a subset \(S\) of indices \(\{i_1, i_2, \dots, i_k\}\) such that for every consecutive indices \(i_j, i_{j+1}\) in \(S\), \(|i_{j+1} - i_j| \ge 2\). The goal is to maximize \(\sum_{i \in S} a_i\), with the restriction that the sum is non-negative (i.e. if no positive sum can be obtained, output 0).

Note: If the array is empty, the result is 0.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\). If \(n = 0\), then there is no second line.

outputFormat

Output a single integer which is the maximum sum of non-adjacent elements from the array.

5
3 2 5 10 7

15