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 ).

Solution 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)

Solution 2

Let A be our input array with zero-based indexing. We can reduce A modulo M without changing the result.

First of all, let's reduce the problem to a slightly easier one by computing an array P representing the prefix sums of A, modulo M:

A = 6 6 11 2 12 1
P = 6 12 10 12 11 12

Now let's process the possible left borders of our solution subarrays in decreasing order. This means that we will first determine the optimal solution that starts at index n - 1, then the one that starts at index n - 2 etc.

In our example, if we chose i = 3 as our left border, the possible subarray sums are represented by the suffix P[3..n-1] plus a constant a = A[i] - P[i]:

a = A[3] - P[3] = 2 - 12 = 3 (mod 13)
P + a = * * * 2 1 2

The global maximum will occur at one point too. Since we can insert the suffix values from right to left, we have now reduced the problem to the following:

Given a set of values S and integers x and M, find the maximum of S + x modulo M

This one is easy: Just use a balanced binary search tree to manage the elements of S. Given a query x, we want to find the largest value in S that is smaller than M - x (that is the case where no overflow occurs when adding x). If there is no such value, just use the largest value of S. Both can be done in O(log |S|) time.

Total runtime of this solution: O(n log n)

Here's some C++ code to compute the maximum sum. It would need some minor adaptions to also return the borders of the optimal subarray:

#include <bits/stdc++.h>
using namespace std;

int max_mod_sum(const vector<int>& A, int M) {
    vector<int> P(A.size());
    for (int i = 0; i < A.size(); ++i)
        P[i] = (A[i] + (i > 0 ? P[i-1] : 0)) % M;
    set<int> S;
    int res = 0;
    for (int i = A.size() - 1; i >= 0; --i) {
        S.insert(P[i]);
        int a = (A[i] - P[i] + M) % M;
        auto it = S.lower_bound(M - a);
        if (it != begin(S))
            res = max(res, *prev(it) + a);
        res = max(res, (*prev(end(S)) + a) % M);
    }
    return res;
}

int main() {
    // random testing to the rescue
    for (int i = 0; i < 1000; ++i) {
        int M = rand() % 1000 + 1, n = rand() % 1000 + 1;
        vector<int> A(n);
        for (int i = 0; i< n; ++i)
            A[i] = rand() % M;
        int should_be = 0;
        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = i; j < n; ++j) {
                sum = (sum + A[j]) % M;
                should_be = max(should_be, sum);
            }
        }
        assert(should_be == max_mod_sum(A, M));
    }
}

Solution 3

For me, all explanations here were awful, since I didn't get the searching/sorting part. How do we search/sort, was unclear.

We all know that we need to build prefixSum, meaning sum of all elems from 0 to i with modulo m

I guess, what we are looking for is clear. Knowing that subarray[i][j] = (prefix[i] - prefix[j] + m) % m (indicating the modulo sum from index i to j), our maxima when given prefix[i] is always that prefix[j] which is as close as possible to prefix[i], but slightly bigger.

E.g. for m = 8, prefix[i] being 5, we are looking for the next value after 5, which is in our prefixArray.

For efficient search (binary search) we sort the prefixes.

What we can not do is, build the prefixSum first, then iterate again from 0 to n and look for index in the sorted prefix array, because we can find and endIndex which is smaller than our startIndex, which is no good.

Therefore, what we do is we iterate from 0 to n indicating the endIndex of our potential max subarray sum and then look in our sorted prefix array, (which is empty at the beginning) which contains sorted prefixes between 0 and endIndex.

def maximumSum(coll, m):
    n = len(coll)
    maxSum, prefixSum = 0, 0
    sortedPrefixes = []

    for endIndex in range(n):
        prefixSum = (prefixSum + coll[endIndex]) % m
        maxSum = max(maxSum, prefixSum)

        startIndex = bisect.bisect_right(sortedPrefixes, prefixSum)
        if startIndex < len(sortedPrefixes): 
            maxSum = max(maxSum, prefixSum - sortedPrefixes[startIndex] + m)

        bisect.insort(sortedPrefixes, prefixSum)

    return maxSum

Solution 4

From your question, it seems that you have created an array to store the cumulative sums (Prefix Sum Array), and are calculating the sum of the sub-array arr[i:j] as (sum[j] - sum[i] + M) % M. (arr and sum denote the given array and the prefix sum array respectively)

Calculating the sum of every sub-array results in a O(n*n) algorithm.

The question that arises is -

Do we really need to consider the sum of every sub-array to reach the desired maximum?

No!

For a value of j the value (sum[j] - sum[i] + M) % M will be maximum when sum[i] is just greater than sum[j] or the difference is M - 1.

This would reduce the algorithm to O(nlogn).

You can take a look at this explanation! https://www.youtube.com/watch?v=u_ft5jCDZXk

Solution 5

There are already a bunch of great solutions listed here, but I wanted to add one that has O(nlogn) runtime without using a balanced binary tree, which isn't in the Python standard library. This solution isn't my idea, but I had to think a bit as to why it worked. Here's the code, explanation below:

def maximumSum(a, m):
    prefixSums = [(0, -1)]
    for idx, el in enumerate(a):
        prefixSums.append(((prefixSums[-1][0] + el) % m, idx))
    
    prefixSums = sorted(prefixSums)
    maxSeen = prefixSums[-1][0]
    
    for (a, a_idx), (b, b_idx) in zip(prefixSums[:-1], prefixSums[1:]):
        if a_idx > b_idx and b > a:
            maxSeen = max((a-b) % m, maxSeen)
            
    return maxSeen

As with the other solutions, we first calculate the prefix sums, but this time we also keep track of the index of the prefix sum. We then sort the prefix sums, as we want to find the smallest difference between prefix sums modulo m - sorting lets us just look at adjacent elements as they have the smallest difference.

At this point you might think we're neglecting an essential part of the problem - we want the smallest difference between prefix sums, but the larger prefix sum needs to appear before the smaller prefix sum (meaning it has a smaller index). In the solutions using trees, we ensure that by adding prefix sums one by one and recalculating the best solution.

However, it turns out that we can look at adjacent elements and just ignore ones that don't satisfy our index requirement. This confused me for some time, but the key realization is that the optimal solution will always come from two adjacent elements. I'll prove this via a contradiction. Let's say that the optimal solution comes from two non-adjacent prefix sums x and z with indices i and k, where z > x (it's sorted!) and k > i:

x ... z
k ... i

Let's consider one of the numbers between x and z, and let's call it y with index j. Since the list is sorted, x < y < z.

x ... y ... z
k ... j ... i

The prefix sum y must have index j < i, otherwise it would be part of a better solution with z. But if j < i, then j < k and y and x form a better solution than z and x! So any elements between x and z must form a better solution with one of the two, which contradicts our original assumption. Therefore the optimal solution must come from adjacent prefix sums in the sorted list.

View more solutions

Comments

[Ankit Roy]

Nice. Also you can make it O(n log min(n, M)) by only inserting distinct sums into the tree.

[Jackery Xu]

in line 5 result should be sum[0]%m, not sum[0]

[ThomasD]

I feel like there is a non-explicit assumption in your explanation regarding S + x mod M reaches its maximum at S = M - 1 - x. If S and x can be any value then S = M - 1 - x + y * M are also valid solutions. In your tree you only store one of them. I think this works out because the x and S are both in [0,M[.

[Niklas B.]

Yes, we're only considering the canonical representatives mod M. Hence the sum of two representatives is in (0, 2M(

[Kalidasan]

looking at this, to me it doesn't seem to be possible that this is a solution since it doesn't even refer to any elements of A apart from A[0]. There's something missing

[Pham Trung]

@dajobe oh, there is a bug in my code, fixed it, thanks :)

[zw0rk]

Why is getMinimumValueLargerThan guaranteed to return something? Suppose, M = 10000000, sequence = [1,1,...]. On the first step when sum[0]=1, tree=[1], sum[1]=2 -- there is no minimum larger than 2 in the tree. Am i mising something?

[Pham Trung]

@zw0rk it is ok if it not return anything, that case is trivial, so I expect you can handle that.

[fons]

I don't understand why you need a full array for the sums if you are only using the last one

[zim32]

Why we have +M in (sum[i] - sum[start] + M) % M. Can't figure out.

[Ravindra M]

Because sum[i] - sum[start] can be negative, hence we add M and take modulo of M to get positive remainder. Also adding any multiples of M would not change the remainder value. 1%7 == (1 + 7)%7 == (1+2*7)%7 etc.

[Nir]

Challenge can be found here: hackerrank.com/challenges/maximum-subarray-sum

[Ghos3t]

"I guess, what we are looking for is clear. Knowing that subarray[i][j] = (prefix[i] - prefix[j] + m) % m (indicating the modulo sum from index i to j),". Where did this equation come from, it's not clear to me?

[denis631]

@Ghos3t basically we just subtract two prefix sums getting the prefix sum of the segment between i and j. Since prefix(i) can be any value between 0 and m, by subtracting the prefix(j) we can get a negative number (if prefix(i) < prefix(j)), this is why we add m, however, the end result will be greater than m if (prefix(i) is > prefix(j)), this is why we perform the % m operation. Nothing fancy, just modulo arithmetic

[cubuspl42]

@zim32 Because we want a modulo operation, which is not present in C/C++ standard library. C / C++ has %, which is a reminder operator. They are quite similar, but not the same; the differences show up on negative numbers. So we implement modulo by hand, and probably the simplest implementation is to use reminder with the + M trick (assuming the addition doesn't overflow). You can read more about modulo/reminder in this answer.

[cubuspl42]

@PhamTrung Just to be sure; Tree has to be a balanced tree for this algorithm to be O(n log n) for arbitrary data, right?