Maximum Sum of Non-Adjacent Items

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

You can solve this problem using dynamic programming. The idea is to define a recurrence relation where the maximum sum up to the i-th element is given by:

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

with appropriate base cases.

Input/Output: The input will be provided via standard input and the result should be printed via standard output.

inputFormat

The first line of input contains a single integer N (0 ≤ N ≤ 10⁵), the number of elements in the list.

The second line contains N space-separated integers, representing the list of numbers.

outputFormat

Output a single integer representing the maximum sum obtainable by selecting non-adjacent items from the list.

5
3 2 5 10 7

15