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

arr = \left[-2, 1, 3, -4, 5 \right]

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.

arr = \left[-2, -3, -1 \right]

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