# HackerRank Max Array Sum Interview preparation kit solution

In this HackerRank Max Array Sum Interview preparation kit problem you have Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset.

## Problem solution in Python programming.

```#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the maxSubsetSum function below.
def maxSubsetSum(arr):
dp = {} # key : max index of subarray, value = sum
dp[0], dp[1] = arr[0], max(arr[0], arr[1])
for i, num in enumerate(arr[2:], start=2):
dp[i] = max(dp[i-1], dp[i-2]+num, dp[i-2], num)
return dp[len(arr)-1]

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

n = int(input())

arr = list(map(int, input().rstrip().split()))

res = maxSubsetSum(arr)

fptr.write(str(res) + '\n')

fptr.close()```

## Problem solution in Java Programming.

```import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

// Complete the maxSubsetSum function below.
static int maxSubsetSum(int[] arr) {
if(arr==null || arr.length==0)
return 0;
int n=arr.length;
if(n==1)
return arr[0];
if(n==2)  //Just for clarification  not really need that
return  Math.max(arr[0],arr[1]);
//will hold all max till the i-th location
int[] g=new int[n];
int currMax = Math.max(arr[0],arr[1]);
g[0]=arr[0];
g[1]=currMax;
for (int i = 2; i < arr.length; i++) {
currMax =  Math.max(g[i-2] + arr[i], currMax);
currMax = Math.max(arr[i], currMax);
g[i]=currMax;

}
return g[n-1];
// return IntStream.of(g).max().getAsInt();
}

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

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

int[] arr = new int[n];

String[] arrItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

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

int res = maxSubsetSum(arr);

bufferedWriter.write(String.valueOf(res));
bufferedWriter.newLine();

bufferedWriter.close();

scanner.close();
}
}
```

### Problem solution in C++ programming.

```#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the maxSubsetSum function below.
int dp[100005];

int maxSubsetSum(vector<int> arr) {

dp[0]=max(0,arr[0]);
if(arr.size()==1)
return dp[0];
for(int i=1;i<arr.size();i++)
{
dp[i]=max(dp[i-2],max(dp[i-1],dp[i-2]+arr[i]));
}
int n=arr.size();
return max(dp[n-1],dp[n-2]);
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

int n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');

string arr_temp_temp;
getline(cin, arr_temp_temp);

vector<string> arr_temp = split_string(arr_temp_temp);

vector<int> arr(n);

for (int i = 0; i < n; i++) {
int arr_item = stoi(arr_temp[i]);

arr[i] = arr_item;
}

int res = maxSubsetSum(arr);

fout << res << "\n";

fout.close();

return 0;
}

vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});

input_string.erase(new_end, input_string.end());

while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}

vector<string> splits;
char delimiter = ' ';

size_t i = 0;
size_t pos = input_string.find(delimiter);

while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));

i = pos + 1;
pos = input_string.find(delimiter, i);
}

splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

return splits;
}
```