HackerRank Maximum Subarray Sum problem solution

In this HackerRank Maximum Subarray Sum Interview preparation kit problem you have Given an n element array of integers, a, and an integer, m, to determine the maximum value of the sum of any of its subarrays modulo m.

Problem solution in Python programming.

from bisect import bisect,insort

T = int(input())
for _ in range(T):
    N,M = [int(i) for i in input().split()]
    ar = [int(i) for i in input().split()]
    
    cumulative_sums = []
    sum_so_far = 0
    max_sum = 0
    
    for i in range(N):
        sum_so_far = (sum_so_far + ar[i]) % M        
        pos = bisect(cumulative_sums, sum_so_far)
        d = 0 if pos == i else cumulative_sums[pos]
        max_sum = max(max_sum, (sum_so_far + M - d) % M)
        insort(cumulative_sums, sum_so_far)
    
    print(max_sum)

Problem solution in Java Programming.

import java.io.*;
import java.util.*;
import java.math.BigInteger;
import java.util.Map.Entry;
import static java.lang.Math.*;

public class Solution {

	long check(long[] a, long m) {
		long ans = 0;
		int n = a.length;

		for (int l = 0; l < n; l++) {
			for (int r = l; r < n; r++) {
				long sum = 0;
				for (int i = l; i <= r; i++) {
					sum = (sum + a[i]) % m;
				}
				if (ans < sum) {
					ans = sum;
				}
			}
		}

		return ans;
	}

	long solve(long[] a, long m) {
		TreeSet<Long> t = new TreeSet<Long>();
		t.add(0L);
		long sum = 0, ans = 0;

		for (long d : a) {
			sum = (sum + d) % m;

			Long x = t.first();
			Long y = t.higher(sum);
			t.add(sum);

			if (x != null) {
				long cur = (sum - x + m) % m;
				if (ans < cur) {
					ans = cur;
				}
			}
			if (y != null) {
				long cur = (sum - y + m) % m;
				if (ans < cur) {
					ans = cur;
				}
			}

		}

		return ans;
	}

	void run() {

		int t = nextInt();

		while (--t >= 0) {
			int n = nextInt();
			long m = nextLong();
			long[] a = new long[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextLong();
			}

			out.println(solve(a, m));

		}
	}

	int[][] nextMatrix(int n, int m) {
		int[][] matrix = new int[n][m];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				matrix[i][j] = nextInt();
		return matrix;
	}

	String next() {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(nextLine());
		return st.nextToken();
	}

	boolean hasNext() {
		while (!st.hasMoreTokens()) {
			String line = nextLine();
			if (line == null) {
				return false;
			}
			st = new StringTokenizer(line);
		}
		return true;
	}

	int[] nextArray(int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = nextInt();
		}
		return array;
	}

	int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	String nextLine() {
		try {
			return in.readLine();
		} catch (IOException err) {
			return null;
		}
	}

	static PrintWriter out;
	static BufferedReader in;
	static StringTokenizer st = new StringTokenizer("");
	static Random rnd = new Random();

	public static void main(String[] args) throws IOException {
		out = new PrintWriter(System.out);
		// out = new PrintWriter(new File("hc.txt"));
		in = new BufferedReader(new InputStreamReader(System.in));
		new Solution().run();
		out.close();
		in.close();
	}
}

Problem solution in C++ programming.

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the maximumSum function below.
long maximumSum(vector<long> vec, long m) {
    
    set<long> ans;
    long global_max,prev_sum, prev_mod, lmax;
    set<long>::iterator itr;
    global_max = prev_mod = vec[0] % m;
    prev_sum = vec[0];
    ans.insert(prev_mod);

    for (unsigned int i=1; i<vec.size(); i++) {
        prev_sum += vec[i];
        prev_mod = prev_sum % m;
        
        // if element greater than prev_mod exists in our set
        if ((itr = ans.upper_bound(prev_mod)) != ans.end()) {
            lmax = (prev_mod - *itr + m) % m;
        }
        else
            lmax = prev_mod;

        ans.insert(prev_mod);
        global_max = max(global_max,lmax); 
    }

    return global_max;
}
int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

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

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string nm_temp;
        getline(cin, nm_temp);

        vector<string> nm = split_string(nm_temp);

        int n = stoi(nm[0]);

        long m = stol(nm[1]);

        string a_temp_temp;
        getline(cin, a_temp_temp);

        vector<string> a_temp = split_string(a_temp_temp);

        vector<long> a(n);

        for (int i = 0; i < n; i++) {
            long a_item = stol(a_temp[i]);

            a[i] = a_item;
        }

        long result = maximumSum(a, m);

        fout << result << "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;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

unsigned long max_sum(
    unsigned long *partial_sums,
    unsigned long *dest,
    unsigned length,
    unsigned long target
) {
    if (length < 2)
        return (*dest = *partial_sums);

    unsigned
        lower_len = length >> 1,
        upper_len = length - lower_len;

    unsigned long
        lower[lower_len],
        upper[upper_len],
        max_left = max_sum(partial_sums, lower, lower_len, target),
        max_right = max_sum(&partial_sums[lower_len], upper, upper_len, target),
        max = max_left > max_right ? max_left : max_right;

    unsigned lesser = 0, greater = 0;

    while (lesser < lower_len && greater < upper_len)
        if (upper[greater] < lower[lesser]) {
            *dest = upper[greater++];
            unsigned long other_max = (*dest++ - lower[lesser]) + target;
            if (other_max > max)
                max = other_max;
        } else
            *dest++ = lower[lesser++];

    memcpy(dest, &lower[lesser], (lower_len - lesser) * sizeof(*dest));
    memcpy(&dest[lower_len - lesser], &upper[greater], (upper_len - greater) * sizeof(*dest));

    return max;
}

int main() {
    unsigned length;
    unsigned long test_case, limit, index;
    static unsigned long
        items[100000],
        buffer[100001] = {[0] = 0},
        *partial_sums = &buffer[1];

    for (scanf("%lu", &test_case); test_case--; ) {
        scanf("%u", &length);
        scanf("%lu", &limit);

        for (index = 0; index < length; index++) {
            scanf("%lu", &items[index]);
            items[index] %= limit;
            partial_sums[index] = (items[index] + partial_sums[index - 1ULL]) % limit;
        }

        // n log n, using partial sums w/ merge sort
        // either the max is in the lower, upper, or some where in between.
        //  find the max of each half,
        //  using sorted order check if the middle max is greater.
        static unsigned long ordered[100000];
        unsigned long max = max_sum(partial_sums, ordered, length, limit);

        // n^2 using partial sums ...
        //unsigned long max = partial_sums[0], chunk, sum, i, j;
        //for (i = 0; i < length; i++)
        //    for (j = i; j < length; j++) {
        //        sum = partial_sums[j] - partial_sums[i - 1];
        //        if (sum > limit) // overflow ...
        //            sum += limit;
        //        if (sum > max)
        //            max = sum;
        //    }

        // brute-force n^3, take max(sum of all possible lengths)
        //unsigned long max = items[0] % limit, chunk;
        //for (index = 1; index < length; index++)
        //    for (chunk = 0; chunk < length/index; chunk++) {
        //        unsigned long total = 0, start;
        //        for (start = chunk * index; start < index; total += items[start++]) ;

        //        total %= limit;
        //        if (total > max)
        //            max = total;
        //    }

        printf("%lun", max);

    }

    return 0;
}

Problem solution in JavaScript programming.

function computeMax(data, modulo) {
    // Compute a modulo sum array. Store an index and a sum.
    var sums = [[-1, 0]];
    var maxSum = 0;
    for (var i=0; i<data.length; i++) {
        sums.push([i, (sums[i][1] + data[i]) % modulo]);
        // One can always compute the difference between 0 and the current element.
        maxSum = Math.max(sums[sums.length-1][1], maxSum);
    }
    // Sort the array by sum value.
    sums.sort(function(a,b){return a[1]-b[1];});
    
    for (var i=1; i<sums.length; i++) {
        var origIndex = sums[i][0],
            curSum = sums[i][1];
        // Look for the first element with greater sum with index before it.
        var j = i+1;
        while (j<sums.length && (sums[j][0] >= origIndex || sums[j][1] == curSum)) {
            j++;
        }
        // If we found one, compute the negative difference and update max.
        if (j<sums.length) {
            maxSum = Math.max(curSum - sums[j][1] + modulo, maxSum);
        }
    }
    return maxSum;
}

function processData(input) {
    var data = input.split("n");
    var t = Number(data[0]);
    for (var i=0; i<t; i++) {
        var m = Number(data[i*2+1].split(" ")[1]);
        var vals = data[i*2+2].split(" ").map(Number);
        console.log(computeMax(vals, m));
    }
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});