Introduction

The maximum subarray sum modulo M problem asks for the largest value of a contiguous subarray sum after applying modulo M. A brute-force scan checks every subarray and quickly becomes too slow. The efficient solution uses prefix sums modulo M plus a sorted set to find the best wraparound candidate in O(n log n) time.

Start from Prefix Sums Modulo M

Let prefix[i] be the sum of elements up to index i, reduced modulo M. Then the sum of subarray i..j modulo M can be derived from two prefix sums.

If prefix[j] >= prefix[i - 1], the subarray modulo is:

prefix[j] - prefix[i - 1]

If prefix[j] < prefix[i - 1], the modulo wraps and becomes:

prefix[j] - prefix[i - 1] + M

That second case is where the optimal answer often comes from, because values close to M - 1 are best.

Why a Sorted Set Solves It

As you scan from left to right, keep all previous prefix sums in sorted order. For the current prefix p, you want the smallest earlier prefix that is strictly greater than p. If you find such a value q, then:

(p - q + M) % M

is a candidate subarray sum modulo M, and it is often very large because q is only slightly larger than p.

At the same time, the prefix p itself is also a candidate, since the subarray may start at index 0.

Efficient Java Implementation

Java's TreeSet is a natural fit because it supports sorted insertion and the higher() lookup.

1import java.util.TreeSet;
2
3public class MaxSubarrayModulo {
4    public static long maximumSum(long[] values, long mod) {
5        TreeSet<Long> prefixes = new TreeSet<>();
6        long best = 0;
7        long prefix = 0;
8
9        for (long value : values) {
10            prefix = (prefix + (value % mod) + mod) % mod;
11            best = Math.max(best, prefix);
12
13            Long nextHigher = prefixes.higher(prefix);
14            if (nextHigher != null) {
15                best = Math.max(best, (prefix - nextHigher + mod) % mod);
16            }
17
18            prefixes.add(prefix);
19        }
20
21        return best;
22    }
23
24    public static void main(String[] args) {
25        long[] values = {3, 3, 9, 9, 5};
26        System.out.println(maximumSum(values, 7)); // 6
27    }
28}

This runs in O(n log n) because each step performs a constant number of TreeSet operations.

Why the Naive Approach Is Too Slow

The brute-force approach checks every subarray:

1def brute_force(arr, mod):
2    best = 0
3    for i in range(len(arr)):
4        total = 0
5        for j in range(i, len(arr)):
6            total += arr[j]
7            best = max(best, total % mod)
8    return best

This is O(n^2), or worse if subarray sums are recomputed from scratch. It is fine for tiny arrays and useful for testing, but it does not scale to typical interview or competitive programming input sizes.

The Key Insight

The clever part is realizing that the maximum modulo value does not always come from the numerically largest raw subarray sum. It comes from choosing two prefix sums whose difference, after wraparound, lands as close as possible to M.

That is why the sorted set lookup matters. You are not just comparing current sums. You are searching for the best earlier prefix to subtract.

Common Pitfalls

The biggest mistake is forgetting that prefix values must stay modulo M at every step. Letting them grow without reduction makes the reasoning and the implementation harder than necessary.

Another issue is using the wrong sorted-set lookup. You want the smallest previous prefix strictly greater than the current prefix, not merely the greatest smaller prefix.

People also often overlook negative values. If the array may contain negatives, normalizing the prefix with + mod before the final modulo keeps the result in the expected range.

Finally, beware of integer overflow in languages with narrow numeric types. Use a sufficiently large integer type for prefix calculations before reducing modulo M.

Summary

• Use prefix sums modulo M to transform subarray sums into prefix differences.
• The best wraparound candidate comes from subtracting the smallest previous prefix greater than the current prefix.
• A sorted structure such as TreeSet makes that lookup efficient.
• The optimal algorithm runs in O(n log n), far better than brute force.
• The hardest part is the prefix-set insight, not the code itself.