# Max Array Sum with Non-adjacent Elements

**Problem Statement**

Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset. It is possible that the maximum sum is 0, the case when all elements are negative.

**Example**

The following subsets with more than 1 element exist. These exclude the empty subset and single element subsets which are also valid.

```
Subset Sum
[-2, 3, 5] 6
[-2, 3] 1
[-2, -4] -6
[-2, 5] 3
[1, -4] -3
[1, 5] 6
[3, 5] 8
```

The maximum subset sum is 8. Note that any individual element is a subset as well.

In this case, it is best to choose no element: return 0.

**Solution**

```
#!/bin/python3
import math
import os
import random
import re
import sys
def maxSubsetSum(a):
dp = [0]
dp[0] = max(0, a[0])
if len(a)==1:
return dp[0]
dp.append(max(dp[0], a[1]))
n = len(a)
for i in range(2,n):
dp.append(max(dp[i-2], max(dp[i-1], dp[i-2]+a[i])))
print(dp)
return max(dp[n-1], dp[n-2])
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
arr = list(map(int, input().rstrip().split()))
res = maxSubsetSum(arr)
fptr.write(str(res) + '\n')
fptr.close()
```