Maximum Sum with No Adjacent Elements

Given an array of integers, your task is to compute the maximum possible sum of a subsequence such that no two selected elements are adjacent in the original array.

You can use dynamic programming with the recurrence: \(dp[i] = \max(dp[i-1], dp[i-2] + a_i)\) for \(i\geq2\), where the initial conditions are \(dp[0] = a_0\) and \(dp[1] = \max(a_0, a_1)\).

inputFormat

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 array elements.

outputFormat

Output a single integer: the maximum sum that can be obtained by selecting non-adjacent elements. If all numbers are negative, output 0.

5
3 2 5 10 7

15