Maximum Sum of Non-Adjacent Elements

You are given a list of non-negative integers. Your task is to compute the maximum sum obtainable by selecting a subset of these numbers such that no two selected numbers are adjacent in the list.

The problem can be solved using dynamic programming with the recurrence relation:

\(dp[i] = \max(dp[i-1],\; dp[i-2] + a_i)\), where \(a_i\) denotes the i-th element of the array. Note that if the list is empty, the answer is 0.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains a single integer n (0 ≤ n ≤ 10⁵) representing the number of elements.
• The second line contains n non-negative integers separated by spaces. If n is 0, the second line may be omitted.

outputFormat

Output to standard output (stdout) a single integer representing the maximum sum obtainable by selecting non-adjacent elements from the list.

5
3 2 5 10 7

15