maximum subarray sum modulo m[Please urgent help]

Правка en1, от acash, 2019-07-12 12:31:34

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

#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;
    }
}
Теги #hackerrank, prefix array

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский acash 2019-07-12 13:15:04 1093
en1 Английский acash 2019-07-12 12:31:34 1178 Initial revision (published)