HackerRank Maximum Subarray Sum Solution

In this post, we will solve HackerRank Maximum Subarray Sum Problem Solution.

We define the following:

A subarray of array a of length n is a contiguous segment from a[i] through a[j] where 0≤ i ≤ j <n.
The sum of an array is the sum of its elements.

Given an n element array of integers, a, and an integer, m, determine the maximum value of the sum of any of its subarrays modulo m.
Example
a = [1, 2, 3]
m = 2
The following table lists all subarrays and their moduli:

		sum	%2
[1]		1	1
[2]		2	0
[3]		3	1
[1,2]		3	1
[2,3]		5	1
[1,2,3]		6	0

The maximum modulus is 1.

Function Description

Complete the maximumSum function in the editor below.

maximumSum has the following parameter(s):

long a[n]: the array to analyze
long m: the modulo divisor

Returns
– long: the maximum (subarray sum modulo m)

Input Format
The first line contains an integer q, the number of queries to perform.
The next a pairs of lines are as follows:

The first line contains two space-separated integers n and (long)m, the length of a and the modulo divisor.
The second line contains n space-separated long integers a[i].

Sample Input

STDIN       Function
-----       --------
1           q = 1
5 7         a[] size n = 5, m = 7
3 3 9 9 5

Sample Output

Explanation
= 7 are The subarrays of array a = [3, 3, 9, 9, 5] and their respective sums modulo m = ranked in order of length and sum in the following list:

[9] 9% 72 and [9] → 9% 7=2 [3] 3% 73 and [3] → 3% 7 = 3 [5] => 5% 75
[9,5] 14% 7=0 [9,9] 18 % 7 = 4 [3,9] 12% 7 = 5 [3, 3] 6% 76
[3,9,9] 21% 7 = 0 [3, 3, 9] 15% 7=1 [9,9,5] 23% 7 = 2
[3, 3, 9, 9] 24% 7 = 3 [3, 9, 9, 5] 26% 7 = 5
[3, 3, 9, 9, 5] 29% 7 = 1
The maximum value for subarray sum % 7 for any subarray is 6.

Table of Contents

Maximum Subarray Sum C Solution

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
typedef unsigned long long bignum;
typedef struct st{
	int index;
	bignum prefix_sum;
}element;
int cmpfunc(const void *a, const void *b)
{
	element x = *(element *)a;
	element y = *(element *) b;
	if(x.prefix_sum < y.prefix_sum) return -1;
	if(x.prefix_sum > y.prefix_sum) return 1;
	if(x.index == y.index) return -1;
	return 0;
}
int main ()
{
	element array[100000];
	int q, n, i, j;
	bignum m, input, min;
	bignum tmp, max = 0;
	scanf("%d", &q);
	for(i = 0; i < q; i++)
	{
		scanf("%d%llu", &n, &m);
		min = m;
		scanf("%llu", &array[0].prefix_sum);
		array[0].prefix_sum %= m;
		max = array[0].prefix_sum;
		array[0].index = 0;
		for(j = 1; j < n; j++)
		{
			scanf("%llu", &input);
			array[j].prefix_sum = (array[j-1].prefix_sum + input) % m;
			array[j].index = j;	
			if(max < array[j].prefix_sum)
				max = array[j].prefix_sum;
		}
		qsort(array, n, sizeof(element), cmpfunc);
		for(j = 1; j < n; j++)
		{
			tmp = array[j].prefix_sum - array[j-1].prefix_sum;
			if(tmp < min)
			{
				if(array[j].index < array[j-1].index) 
				{
					min = tmp;
				}
			}
		}
		printf("%llu\n", max > m - min ? max : m - min);
	}
	return EXIT_SUCCESS;
}

Maximum Subarray Sum C++ Solution

#include<iostream>
#include<cstdio>
#include<set>

using namespace std;

set< long long > secik;
set< long long >::iterator it;
long long n, m, t, sum, x, ans;

int main()
{
	cin>>t;
	while( t-- )
	{
		cin>>n>>m;
		secik.clear();
		secik.insert( 0 );
		sum = 0;
		ans = 0;
		for( int a = 1; a <= n; a++ )
		{
			cin>>x;
			sum += x;
			sum %= m;
//			cout<<sum<<endl;
			it = secik.lower_bound( m - sum );
			it--;
//			cout<<a<<" "<<*it<<endl;
			ans = max( ans, ( sum + *it ) % m );
			secik.insert( ( -sum + m ) % m );
		}
		cout<<ans<<endl;
	}

	return 0;	
}

Maximum Subarray Sum C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
        private class Prefix : IComparable
        {
            public long Sum { get; set; }
            public int Position { get; set; }

            public int CompareTo( object obj )
            {
                int sumRes = this.Sum.CompareTo( ((Prefix)obj).Sum );
                if (sumRes == 0)
                {
                    return this.Position.CompareTo( ((Prefix)obj).Position );
                }
                else
                {
                    return this.Sum.CompareTo( ((Prefix)obj).Sum );
                }
            }
        }
    
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        
            int t = Int32.Parse( Console.ReadLine().Trim() );
            for (int it = 0; it < t; it++)
            {
                string[] nm = Console.ReadLine().Trim().Split();
                long n = Int64.Parse( nm[ 0 ] );
                long m = Int64.Parse( nm[ 1 ] );

                long[] a = Array.ConvertAll<string, long>( Console.ReadLine().Trim().Split(), ( str ) => Int64.Parse( str ) % m );

                Prefix[] prefixes = new Prefix[ n ];

                prefixes[ 0 ] = new Prefix() { Sum = a[ 0 ], Position = 0 };
                for (int i = 1; i < n; i++)
                {
                    prefixes[ i ] = new Prefix() { Sum = (prefixes[ i - 1 ].Sum + a[ i ]) % m, Position = i };
                }

                Array.Sort<Prefix>( prefixes );

                long min = -1;

                for (int i = 0; i < n - 1; i++)
                {
                    if (prefixes[ i ].Position > prefixes[ i + 1 ].Position && (prefixes[ i + 1 ].Sum - prefixes[ i ].Sum < min || min == -1))
                    {
                        min = prefixes[ i + 1 ].Sum - prefixes[ i ].Sum;
                    }
                }

                if (prefixes[ n - 1 ].Sum > m - min || min == -1) min = m - prefixes[ n - 1 ].Sum;

                Console.WriteLine( "{0}", m - min );
            }
    }
}

Maximum Subarray Sum Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'maximumSum' function below.
     *
     * The function is expected to return a LONG_INTEGER.
     * The function accepts following parameters:
     *  1. LONG_INTEGER_ARRAY a
     *  2. LONG_INTEGER m
     */

    public static long maximumSum(List<Long> a, long m) {
    // Write your code here
      long max = 0 , curr = 0; 
        TreeSet<Long> t = new TreeSet<>();
        for (int i=0; i<a.size(); i++){
            curr = (curr + a.get(i) % m) % m;
            max = Math.max(max , curr);
            Long p = t.higher(curr);
            if (p!=null){
                max = Math.max(max , (curr-p+m)%m);
            }
            t.add(curr);
        }
            return max;

 
    
   
    }

}


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

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                int n = Integer.parseInt(firstMultipleInput[0]);

                long m = Long.parseLong(firstMultipleInput[1]);

                List<Long> a = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                    .map(Long::parseLong)
                    .collect(toList());

                long result = Result.maximumSum(a, m);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Maximum Subarray Sum JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the maximumSum function below.
function maximumSum(a, m) {
    for (var accum = 0, i = 0; i < a.length; i++) {
        accum = a[i - 1] !== undefined ? a[i - 1][1] : 0;
        a[i] = [i, (parseInt(a[i]) + accum) % m];
    }
    a.sort(function (a, b) {
        return a[1] - b[1]
    });
    var min = m;
    var sign = 1, diff;
    for (var d = 1; d < a.length; d++) {
        sign = a[d][0] > a[d - 1][0] ? 1 : -1
        diff = sign * (a[d - 1][1] - a[d][1]);
        if (diff > 0) {
            min = diff < min ? diff : min;
        }
    }
    var right = a[a.length - 1][1];
    var left = m - min;
    return (right > left ? right : left);
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const q = parseInt(readLine(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const nm = readLine().split(' ');

        const n = parseInt(nm[0], 10);

        const m = parseInt(nm[1], 10);

        const a = readLine().split(' ').map(aTemp => parseInt(aTemp, 10));

        let result = maximumSum(a, m);

        ws.write(result + "\n");
    }

    ws.end();
}

Maximum Subarray Sum Python Solution

from bisect import bisect_right

def solve(ar, m):
    # create prefix list
    p = [0]
    for x in ar:
        p.append((p[-1]+x)%M)
    # find lowest diff
    d = m-max(p)
    pre = [0]
    for j in range(1, len(ar)+1):
        if p[j] < pre[-1]:
            i = bisect_right(pre, p[j])
            d = min(d, pre[i]-p[j])
            pre.insert(i, p[j])
        else:
            pre.append(p[j])
    return m-d
        

for T in range(int(input())):
    N, M = [int(x) for x in input().split()]
    ar = [int(x) for x in input().split()]
    print(solve(ar, M))