Maximum Non-Adjacent Subsequence Sum

You are given an array of integers. Your task is to find the maximum sum of a subsequence such that no two numbers in the subsequence are adjacent in the original array. If all numbers are negative, the answer should be 0.

Problem Details:

• You cannot pick two adjacent elements.
• If the array is empty or if picking any element decreases the sum below 0, output 0.

Note: Use dynamic programming to efficiently solve this problem, as the size of the input may be large.

inputFormat

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

outputFormat

Output a single integer representing the maximum sum of a subsequence with non-adjacent elements.## sample

5
3 2 5 10 7

15