- Prepare
- Interview Preparation Kit
- Dynamic Programming
- Max Array Sum

# 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. It is possible that the maximum sum is , the case when all elements are negative.

**Example**

The following subsets with more than 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 . Note that any individual element is a subset as well.

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

**Function Description**

Complete the function in the editor below.

maxSubsetSum has the following parameter(s):

*int arr[n]:*an array of integers

**Returns**

- *int:* the maximum subset sum

**Input Format**

The first line contains an integer, .

The second line contains space-separated integers .

**Constraints**

**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.