We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Maximum Subarray Sum

Maximum Subarray Sum

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

We define the following:

  • A subarray of array of length is a contiguous segment from through where .
  • The sum of an array is the sum of its elements.

Given an element array of integers, , and an integer, , determine the maximum value of the sum of any of its subarrays modulo .

Example

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 .

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 )

Input Format

The first line contains an integer , the number of queries to perform.

The next pairs of lines are as follows:

  • The first line contains two space-separated integers and (long), the length of and the modulo divisor.
  • The second line contains space-separated long integers .

Constraints

  • the sum of over all test cases

Sample Input

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

Sample Output

6

Explanation

The subarrays of array and their respective sums modulo are ranked in order of length and sum in the following list:

  1. and
    and






The maximum value for for any subarray is .

Author

devuy11

Difficulty

Hard

Max Score

65

Submitted By

49898

Need Help?


View discussions
View editorial
View top submissions
RESOURCES

  • Binary Search

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy