Maximum Non-Adjacent Sum

Given an array of integers, your task is to determine the maximum sum obtainable by selecting non-adjacent elements. In other words, if you select an element at index (i), you cannot select the element at index (i+1). The problem can be formulated using the recurrence relation:

[ \text{dp}[i] = \max(\text{dp}[i-1],; \text{dp}[i-2] + a_i) \quad\text{for } i \geq 2 ]

with base cases (\text{dp}[0] = \max(0, a_0)) and (\text{dp}[1] = \max(\text{dp}[0], a_1)) (if (a_1) is positive). This ensures that when dealing with negative numbers the solution returns 0 if no positive sum can be formed. The input might be an empty list, which should yield 0 as the result. This problem is typical of dynamic programming challenges and requires careful handling of edge cases.

inputFormat

The input is provided via standard input (stdin) and consists of two lines:

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

If (n = 0), the second line may be omitted.

outputFormat

Output a single integer to standard output (stdout) which is the maximum sum obtainable by picking non-adjacent elements from the array.## sample

5
3 2 5 10 7

15