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