Cerinta completa

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 .

Limbajul de programare folosit: java8

Cod:

import java.util.Arrays;
import java.util.NavigableSet;
import java.util.Scanner;
import java.util.TreeSet;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int q = sc.nextInt();
		for (int tc = 0; tc < q; tc++) {
			int n = sc.nextInt();
			long m = sc.nextLong();
			long[] a = new long[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = sc.nextLong();
			}

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

		sc.close();
	}

	static long solve(long[] a, long m) {
		long[] sums = buildSums(a, m);

		long result = Arrays.stream(sums).max().getAsLong();
		NavigableSet<Long> sortedSums = new TreeSet<>();
		for (long sum : sums) {
			Long higher = sortedSums.higher(sum);
			if (higher != null) {
				result = Math.max(result, addMod(sum, -higher, m));
			}

			sortedSums.add(sum);
		}
		return result;
	}

	static long[] buildSums(long[] a, long m) {
		long[] sums = new long[a.length];
		long sum = 0;
		for (int i = 0; i < sums.length; i++) {
			sum = addMod(sum, a[i], m);
			sums[i] = sum;
		}
		return sums;
	}

	static long addMod(long x, long y, long modulus) {
		return ((x + y) % modulus + modulus) % modulus;
	}
}

Scor obtinut: 1.0

Submission ID: 464602873

Link challenge: https://www.hackerrank.com/challenges/maximum-subarray-sum/problem

Maximum Subarray Sum