HackerRank Max Array Sum problem solution

In this HackerRank Max Array Sum problem solution, given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset. It is possible that the maximum sum is 0, the case when all elements are negative.

Function Description

Complete the maxSubsetSum function in the editor below.

maxSubsetSum has the following parameter(s):

• int arr[n]: an array of integers

Returns
– int: the maximum subset sum

HackerRank Max Array Sum problem solution in Python.

#!/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()

Max Array Sum problem solution in Java.

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("(rn|[nru2028u2029u0085])?");

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(rn|[nru2028u2029u0085])?");

        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;
}