I was trying to solve a problem problem link

This problem is also on hackerrank

I am failing in some test cases I used the approach given in above link

MY solution

Method (efficient approach): The idea is to compute prefix sum of array. We find maximum sum ending with every index and finally return overall maximum. To find maximum sum ending at index at index, we need to find the starting point of maximum sum ending with i. Below steps explain how to find the starting point.

Let prefix sum for index i be prefixi, i.e., prefixi = (arr[0] + arr[1] + .... arr[i] ) % m

Let maximum sum ending with i be, maxSumi. Let this sum begins with index j.

maxSumi = (prefixi — prefixj + m) % m

From above expression it is clear that the value of maxSumi becomes maximum when prefixj is greater than prefixi and closest to prefix[i We mainly have two operations in above algorithm.

1)Store all prefixes. 2)For current prefix, prefix[i], find the smallest value greater than or equal to prefix[i] + 1. For above operations, a self-balancing-binary-search-trees like AVL Tree, Red-Black Tree, etc are best suited. In below implementation we use set in STL which implements a self-balancing-binary-search-tree.

#include <bits/stdc++.h>

using namespace std;


// Complete the maximumSum function below.
long maximumSum(vector<long> &a, long m) {
    set<long> seen;
    //prefix[0]=a[0]%m;
    long sum = a[0]%m;
    long ans=0;
    long maxx = 0;
    for(long i=1;i<a.size();i++){
        sum = (sum%m + a[i]%m)%m;
        maxx = max(sum,maxx); 
        auto it  =  seen.lower_bound(sum+1);
        if(it!=seen.end()){
            ans = max(ans,(sum-(*it)+m));
        }
        seen.insert(sum);
    }
    return max(ans,maxx);

}

int main(){
    long n,k;
    long q;
    cin>>q;
    while(q--){
    cin>>n>>k;
    vector<long> a;
    for(long i=0;i<n;i++){
        long u;
        cin>>u;
        a.push_back(u);
    }
    cout<<maximumSum(a,k)<<endl;
    }
}