Maximum Sum of Non-Adjacent Elements
Given an array, find the maximum sum of a subsequence with no two adjacent elements chosen.
Input format
The first line contains N. The second line contains N integers (0–100).
Output format
Print maximum sum of non-adjacent elements (empty selection allowed → ≥0).
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
5
5 5 10 100 10Expected output
105Example 2
Input
3
1 2 3Expected output
4