## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# 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()