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.
  1. Prepare
  2. Algorithms
  3. Search
  4. Maximum Subarray Sum

Maximum Subarray Sum

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 .