Maximum Non-Adjacent Subset Sum

You are given an array of non-negative integers. Your task is to find the maximum sum of a subset of these integers such that no two elements chosen are adjacent in the original array.

In other words, if the array is denoted by (a_1, a_2, \ldots, a_n), you need to select a set of indices (I) such that for any two indices (i, j \in I) with (|i-j| = 1) the elements are not both selected, and the sum (\sum_{i \in I} a_i) is maximized. This is a typical dynamic programming problem.

inputFormat

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated non-negative integers.

outputFormat

Output a single integer, which is the maximum sum achievable by selecting non-adjacent elements from the array.## sample

1
5

5