Maximum Sum of Non-Adjacent Elements

You are given an array of N integers. Your task is to select a subset of these integers such that no two chosen elements are adjacent in the original array, and the sum of the chosen elements is maximized.

More formally, consider an array \(A = [a_1, a_2, \dots, a_N]\). You need to choose a set of indices \(I = \{i_1, i_2, \dots, i_k\}\) where for every consecutive pair \(i_j\) and \(i_{j+1}\) in \(I\), it holds that \(i_{j+1} - i_j > 1\). The goal is to maximize the sum:

[ S = \sum_{j=1}^{k} a_{i_j} ]

Note that if the array is empty, you must output 0.

Hint: A dynamic programming solution can be used. Define the recurrence:

[ dp[i] = \max(dp[i-1], dp[i-2] + a_i), ]

where \(dp[i]\) represents the maximum sum that can be achieved considering the first \(i\) elements. The answer will be \(dp[N]\). Ensure that your solution correctly handles edge cases (such as an empty array).

inputFormat

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

outputFormat

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

## sample

5
3 2 5 10 7

15