Maximum Subset Sum With No Adjacent Elements

You are given an array of integers. Your task is to find the maximum sum of a subset of these integers such that no two elements in the subset are adjacent in the original array.

Formally, given an array \(A\) of length \(n\), choose a subset of indices \(S\) such that for every two indices \(i, j \in S\) we have \(|i - j| > 1\), and maximize \(\sum_{i \in S} A[i]\). If the array is empty, the answer is 0.

This problem can be solved efficiently using dynamic programming.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array. If \(n > 0\), the second line contains \(n\) space-separated integers.

outputFormat

Output a single integer, the maximum sum of a subset of non-adjacent elements.

5
3 2 5 10 7

15