Maximum subarray sum modulo M

We can do this as follow:

Maintaining an array sum which at index ith, it contains the modulus sum from 0 to ith.

For each index ith, we need to find the maximum sub sum that end at this index:

For each subarray (start + 1 , i ), we know that the mod sum of this sub array is

int a = (sum[i] - sum[start] + M) % M

So, we can only achieve a sub-sum larger than sum[i] if sum[start] is larger than sum[i] and as close to sum[i] as possible.

This can be done easily if you using a binary search tree.

Pseudo code:

int[] sum;
sum[0] = A[0];
Tree tree;
tree.add(sum[0]);
int result = sum[0];
for(int i = 1; i < n; i++){
    sum[i] = sum[i - 1] + A[i];
    sum[i] %= M;
    int a = tree.getMinimumValueLargerThan(sum[i]);
    result = max((sum[i] - a + M) % M, result);
    tree.add(sum[i]);
}
print result;

Time complexity :O(n log n)