Maximum subarray sum modulo M

Question

Most of us are familiar with the maximum sum subarray problem. I came across a variant of this problem which asks the programmer to output the maximum of all subarray sums modulo some number M.

The naive approach to solve this variant would be to find all possible subarray sums (which would be of the order of N^2 where N is the size of the array). Of course, this is not good enough. The question is - how can we do better?

Example: Let us consider the following array:

6 6 11 15 12 1

Let M = 13. In this case, subarray 6 6 (or 12 or 6 6 11 15 or 11 15 12) will yield maximum sum ( = 12 ).

Answer 1

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)