We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Interview Preparation Kit
  3. Dynamic Programming
  4. Max Array Sum

Max Array Sum

Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset.

For example, given an array we have the following possible subsets: 

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

Our maximum subset sum is .

Function Description

Complete the function in the editor below. It should return an integer representing the maximum subset sum for the given array.

maxSubsetSum has the following parameter(s):

  • arr: an array of integers

Input Format

The first line contains an integer, .
The second line contains space-separated integers .

Constraints

Output Format

Return the maximum sum described in the statement.

Sample Input 0

5
3 7 4 6 5

Sample Output 0

13

Explanation 0

Our possible subsets are and . The largest subset sum is from subset

Sample Input 1

5
2 1 5 8 4

Sample Output 1

11

Explanation 1

Our subsets are and . The maximum subset sum is from the first subset listed.

Sample Input 2

5
3 5 -7 8 10

Sample Output 2

15

Explanation 2

Our subsets are and . The maximum subset sum is from the fifth subset listed.