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[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. #blog #interview #placement #learn #computer #science

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door