Maximum sub array modulo using Kadane algorithm

Question

I am trying to solve hackerrank problem - Maximum sub array modulo - described here https://www.hackerrank.com/challenges/maximum-subarray-sum/problem. I am curious if this problem can be solved with Kadane algorithm.

The goal: given an n-element array of integers, and an integer 'm' , determine the maximum value of the sum of any of its subarrays modulo 'm'.

Input Format:

1) First line contains an integer 'q' denoting the number of queries to perform. Each query is described over two lines:

a) The first line contains two space-separated integers describing - array length and modulo number.

b) The second line contains space-separated integers describing the elements of array.

Here is the likely C++ code that I came up . It fails for some of the test cases (sorry the test cases are too large to post here). Could you comment/review as why this may not work? Thanks.

#include <bits/stdc++.h>

int main()
{
    uint64_t q = 0, n = 0, m = 0;

    std::cin >> q;
    std::cin >> n;
    std::cin >> m;

    while(q) {
        std::vector<uint64_t> vec;
        for (uint64_t i = 0; i < n; i++) {
            uint64_t num;
            std::cin >> num;
            vec.push_back(num);
        }
        uint64_t subArrayMax = 0;
        uint64_t maxMod = 0;
        for (uint64_t i = 0; i < n; i++) {
            // Kadane's algorithm.
            subArrayMax = std::max(subArrayMax, subArrayMax+vec[i]); // try (a+b)%m=(a%m+b%m)%m trick?
            maxMod = std::max(maxMod, subArrayMax % m);
        }
        std::cout << maxMod;
        --q;
    }
}

Answer 1

Kadane's algorithm is not working here because it involves property of modular arithmetic.

First you have to understand why Kadane's algorithm works: It is a simple dynamic programming which answers the following question:

If we know the maximum sum end at index i-1, then maximum sum end at i is either append a[i] to the subarray yielding answer at i-1, OR not appending it

With modular arithmetic, this does not work. For eg:

Let A = {1,2,3,4}, M = 6

With Kadane's algorithm, of course, maximum sum is adding all elements, and it can be found using the thought quoted above: Keep appending a[i] into previous maximum sum found.

But if we are finding maximum sum % 6, then answer is (2+3)%6 = 5 but not (1+2+3)%6 = 0 or (1+2+3+4)%6 = 4. The larger the maximum sum NOT IMPLIES a more optimal sum for maximum sum % M. Therefore your goal here is not even finding maximum sum.

---

This problem can be solved in O(N lg N) using a modified version of Kadane's algorithm.

For a specific index i,

Let DP(i) = maximum subarray sum % M end at i

Let PS(i) be the prefix sum % M end at i

Naturally you will start to think how to find some j < i which (PS(i) - PS(j)+ M) % M is maximum. (Assume you know how to precompute PS and basic modular arithmetic)

---

Here is the core part: turns out

DP(i) = max(PS(i), (PS(i) - PS(j) + M) % M

Where PS(j') is the smallest number larger than PS(i) out of all j < i

Why? Because look at the formula, if PS(j') < PS(i), then it is of course better NOT TO minus anything from PS(i).

However if PS(j') > PS(i), then we can rewrite the formula like this: (M - x)%M, then we want x = PS(j')-PS(i) as small as possible, so that (M - x)%M is the largest.

Same as Kadane's algorithm, we keep track the maximum answer found along the process.

We can use priority queue or set data structure to find such j' for all i online, achieving O(N lg N) in total. Details you can see below accepted code:

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

int T;
set<LL> pre;
LL n, M, a[100010], ans, sum;

int main() {
    cin >> T;
    while(T--){
        ans = sum = 0;
        pre.clear();
        cin >> n >> M;
        for(int i=0; i<n;i++) cin >> a[i];
        for(int i=0; i<n; i++){
            (sum += a[i]) %= M;
            ans = max(ans, sum);
            ans = max(ans, (sum - *(pre.upper_bound(sum))+M)%M);
            pre.insert(sum);
        }
        cout << ans << endl;
    }
    return 0;
}