Maximum Non-Adjacent Sum

You are given an array of n integers. Your task is to compute the maximum sum of a subsequence such that no two numbers in the subsequence are adjacent in the original array.

Note: The array may contain zero or more elements. If the array is empty, the maximum sum is 0.

Example:

Input:
4
3 2 7 10
Output:
13

In this example, selecting elements 3, 7, and 10 would violate the non-adjacency condition. The optimal selection is 3 and 10, with a sum of 13, or 3, 7, which gives 10. However, the best combination here is 3 + 10 = 13 (since 2 and 7 yield less). We expect you to implement an efficient solution using dynamic programming.

inputFormat

The first line of input contains a single integer n which is the number of elements in the array. If n is positive, the second line contains n space-separated integers representing the array elements. If n is 0, the array is empty.

outputFormat

Output a single integer which is the maximum sum of non-adjacent elements from the given array.

4
3 2 7 10

13