Maximum Non-Consecutive Subsequence Sum

Given an array of integers A with size N, your task is to find the maximum sum obtainable by selecting a non-empty subsequence of elements such that no two chosen elements are consecutive in the original array.

You can think of this as a variation of the House Robber problem. Mathematically, the recurrence relation is given by:

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

with the initial conditions defined appropriately. Note that the subsequence must contain at least one element.

inputFormat

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

outputFormat

Output a single integer, the maximum sum of a non-empty subsequence in which no two elements are consecutive.

4
3 2 7 10

13