Search

# HackerRank | Max Array Sum

In this blog, we will discuss the Max Array sum problem asked in HackerRank.

### Problem Description:

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 arr = [-2, 1, 3, -4, 5] 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 8.

### Function Description:

Complete the maxSubsetSum 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, n. The second line contains n space-separated integers arr[I].

### Constraints:

• 1 <= n <= 10^5

• -10^4 <= arr[I] <= 10^4

### 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 [3, 4, 5], [3, 4], [3, 6], [3, 5], [7, 6], [7, 5] and [4, 5] . The largest subset-sum is 13 from the subset [7, 6]

Sample Input 1

```5
2 1 5 8 4 ```

Sample Output 1

`11 `

Explanation 1

Our subsets are [2, 5, 4], [2,5], [2, 8], [2, 4], [1, 8], [1, 4] and [5, 4]. The maximum subset-sum is 11 from the first subset listed.

Sample Input 2

```5
3 5 -7 8 10 ```

Sample Output 2

`15 `

Explanation 2

Our subsets are [3, -7, 10], [3, 8], [3, 10], [5, 8] and [-7, 10] . The maximum subset-sum is 15 from the fifth subset listed.

### Implementation using java 8:

```import java.io.*;
import java.math.*;
import java.util.*;

public class Solution {

static int maxSubsetSum(int arr[], int n)
{
int incl = arr;
int excl = 0;
int excl_new;
int i;

for (i = 1; i < n; i++)
{
/* current max excluding i */
excl_new = (incl > excl) ? incl : excl;

/* current max including i */
incl = excl + arr[i];
excl = excl_new;
}

/* return max of incl and excl */
return ((incl > excl) ? incl : excl);
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {

int n = scanner.nextInt();
scanner.nextLine();
int[] arr = new int[n];

String[] arrItems = scanner.nextLine().split(" ");

for (int i = 0; i < n; i++) {
int arrItem = Integer.parseInt(arrItems[i]);
arr[i] = arrItem;
}

int res = maxSubsetSum(arr,arr.length);

printf("%d",res);
scanner.close();
}
}```

Happy Coding!

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

See All