.png)
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[0];
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!
Follow us on Instagram @programmersdoor
Join us on Telegram @programmersdoor
Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.
Follow Programmers Door for more.