Maximum Sum of Non-Adjacent Subarray

Given an array of n integers, the task is to find the maximum sum of a subsequence such that no two elements in the subsequence are adjacent in the original array. In other words, if you select an element a_i, you cannot select a_i-1 or a_i+1 for the sum.

This can be formulated using dynamic programming. Let \(dp[i]\) represent the maximum sum obtainable considering the first \(i+1\) elements. The recurrence relation is given by:

\( dp[i] = \max(dp[i-1], dp[i-2] + a_i) \quad \text{for } i \geq 2, \)

with base cases \(dp[0] = a_0\) and \(dp[1] = \max(a_0, a_1)\) (assuming \(n \geq 2\)).

inputFormat

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

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

outputFormat

Output a single integer representing the maximum sum of a subsequence with the constraint that no two consecutive elements are selected. The result should be printed to stdout.

5
3 2 5 10 7

15