Maximum Non-Adjacent Subset Sum

You are given an array of integers. Your task is to find the maximum possible sum of a subset of non-adjacent elements. In other words, you need to choose a subset of the array such that no two chosen elements are consecutive in the original array, and the sum of the chosen elements is maximized.

Note: It is allowed to choose an empty subset, which has a sum of 0. This is particularly useful when all the elements in the array are negative.

Constraints:

• 1 ≤ n ≤ 10⁵
• Each element of the array is an integer (it may be negative or positive).

The problem can be solved using dynamic programming by keeping track of the maximum sum including or excluding each element.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer n, the number of elements in the array. The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer to standard output (stdout) which is the maximum sum obtainable by selecting a subset of non-adjacent elements. If no positive sum can be achieved, output 0.## sample

4
3 2 7 10

13