Problem :

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


My Solution :

#!/usr/bin/env python3

def maximumSum(a, m):
    s = 0
    pfs = []
    for i in range(len(a)):
        s = (s + a[i]%m)%m
        if s == m - 1: return s
        pfs.append((i, s))
    pfs = sorted(pfs, key=lambda x: x[1])
    min_d = m
    max_s = 0
    for i in range(len(pfs) - 1):
        if 0 < pfs[i+1][1] - pfs[i][1] < min_d and pfs[i][0] > pfs[i+1][0]:
            min_d = pfs[i+1][1] - pfs[i][1]
            max_s = pfs[i][1] - pfs[i+1][1] + m
    return max(max_s, pfs[-1][1])


q = int(input())
for _ in range(q):
    n, m = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    print(maximumSum(a, m))