Maximum Sum of Non-Adjacent Elements

Given an array of positive integers, compute the maximum sum that can be obtained by selecting non-adjacent elements. In other words, no two selected elements should be consecutive in the array.

You can solve this problem using dynamic programming. One common recurrence is given by: $$dp[i] = \max(dp[i-1], dp[i-2] + arr[i])$$, where $$dp[i]$$ represents the maximum sum achievable using elements up to the index i.

Your task is to implement an efficient algorithm to compute this maximum sum.

inputFormat

The input is read from standard input (stdin) and 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 positive integers, which are the elements of the array.

outputFormat

Output a single integer to standard output (stdout), which is the maximum sum of non-adjacent elements from the array.## sample

0

0