Maximum Non-Adjacent Sum

You are given an array of integers. Your task is to select a subset of these integers such that no two selected integers are adjacent in the original array and the sum of the selected integers is maximized.

This problem can be solved using dynamic programming. Define a DP formulation: \(dp[i] = \max(dp[i-1], dp[i-2] + a_i)\), where \(a_i\) is the \(i^{th}\) element of the array.

For example, given the array [3, 2, 5, 10], the maximum sum is 13 by choosing elements 3 and 10.

inputFormat

The input consists of two lines. The first line contains a single integer \(N\) representing the number of elements in the array. The second line contains \(N\) space-separated integers.

If \(N = 0\), the array is empty.

outputFormat

Output a single integer representing the maximum sum obtainable by summing non-adjacent numbers from the array.

4
3 2 5 10

13