Reputation: 529
The question is - You are given an array of size N and another integer M. Your target is to find the maximum value of sum of subarray modulo M.
If array is {3 3 9 9 5} and M is {7}
Possible subarrays are
{3},{3},{9}.{9}.{5}
{3,3},{3,9},{9,9},{9,5}
{3,3,9},{3,9,9},{9,9,5}
{3,3,9,9},{3,9,9,5},{3,3,9,9,5}
out of which max possible sum taking modulo 7 will be 6. Subarray {3,3} has the maximum sum.
I came across the solution, but unable to understand the logic
static void solve(long M, long[] array){
TreeSet<Long> sumSet = new TreeSet<Long>();
long best = 0;
long sum = 0;
for(int i = 0; i < array.length; i++){
sum = (sum + array[i]) % M;
Long up = sumSet.higher(sum);
if(up == null){
best = Math.max(best,sum);
} else {
best = Math.max(best, M - up + sum);
}
sumSet.add(sum);
}
System.out.println(best);
}
What does the line mean
best = Math.max(best, M - up + sum);
Upvotes: 1
Views: 1350
Reputation: 2435
In modular arithmetic, adding the divisor to the result doesn't make a difference. For example, -1 (mod N)
is same as N-1
.
In your algorithm, M - up + sum
is subtracting up
from sum
and since it will always be negative, adds M
to make the result positive.
What the algorithm is doing?
sum
sum
into a TreeSet
. The idea is to be able to extract a sum in O(log N)
. sum - (any number from sumSet)
is the sum of a sub-array. If the result is negative, adding up M
gives a positive sum of the sub-array. sum
from sumSet
. Why? The maximum sum possible is the least negative. The maximum modulo sum possible is M - 1
. It is obtained when sum - up
is equal to -1
. sum
with the best
.sum - up + M
with best
.Complexity: O(n log n)
Upvotes: 1