# 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>();
long sum = 0, ans = 0;

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

Long x = t.first();
Long y = t.higher(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 {
} catch (IOException err) {
return null;
}
}

static PrintWriter out;
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"));
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("%lu\n", 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);
});