Maximum Sum of Non-Adjacent Subsequence

Given an array of integers, find the maximum possible sum of a non-empty subsequence such that no two numbers in the subsequence are adjacent in the original array.

If the array is empty or if all selections yield negative values, the answer is defined as 0. You can solve this problem using dynamic programming with the recurrence relation:

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

Ensure your solution reads input from stdin and writes output to stdout.

inputFormat

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

outputFormat

Output a single integer which is the maximum sum of a subsequence where no two chosen numbers are adjacent in the array.## sample

5
3 2 5 10 7

15