Maximum Non-Adjacent Subsequence Sum

Given a sequence of integers, determine the maximum sum that can be obtained by choosing a subsequence such that no two chosen elements are adjacent in the original sequence. In other words, if you select an element at index i, you cannot select elements at index i-1 or i+1. Note that if all numbers are negative, the answer should be 0 (by choosing an empty subsequence).

The problem can be mathematically formulated as follows:

$$\text{Let } a_1, a_2, \dots, a_n \text{ be the given sequence. Compute } \max_{S \subseteq \{1,2,\ldots,n\}, \text{ no adjacent indices in } S} \sum_{i \in S} \max(a_i,0)$$

Consider the following examples:

• Input: [3, 2, 5, 10, 7] → Output: 15
• Input: [-1, -2, -3] → Output: 0
• Input: [5] → Output: 5

Your task is to implement a program that reads an integer n followed by n space-separated integers and outputs the maximum non-adjacent subsequence sum. ## inputFormat The first line of input contains a single integer n — 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 of a non-adjacent subsequence satisfying the condition described in the problem.## sample

5
3 2 5 10 7

15

$$