Maximum Sum of Non-Adjacent Elements

Given a list of non-negative integers representing weights, you are required to select a subset such that no two selected numbers are adjacent in the list, and the sum of the selected numbers is maximized.

Note: Consider the array indices starting from 0. If you select an element at index i, you cannot select the elements at indices i-1 and i+1.

The solution should be efficient and work for large inputs.

Mathematically, the problem is to maximize \( S = \sum_{i \in I} a_i \) subject to \( \forall i,\; i \in I \Rightarrow (i-1 \notin I \,\text{and}\, i+1 \notin I) \).

inputFormat

The first line of input contains a single integer \( n \) representing the number of elements in the array. The second line contains \( n \) space-separated integers representing the weights.

If \( n = 0 \), then the second line will be empty.

outputFormat

Output a single integer representing the maximum sum of weights from the subset of non-adjacent elements.

1
5

5