CODEWITHSUNDEEP
arraysdynamic-programming
Ad-vic
Ad-vic

Reputation: 529

find the maximum value of sum of subarray modulo M

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

Answers (1)

Mukul Gupta
Mukul Gupta

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?

  • Iterate over the array and maintain a running sum using the variable sum
  • Keep storing the running 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.
  • Extract the least integer greater than 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.
  • If there is no such previous sum, compare the present sum with the best.
  • Else, compare sum - up + M with best.

Complexity: O(n log n)

Upvotes: 1

Related Questions