Subarray_Maximum_sum %M

Related Question:-

https://www.hackerrank.com/contests/101hack21/challenges/maximise-sum



If  an array contains only positive elements and it is told to find maximum sum of array % M, Then this method can be used.

    ( In case of negative elements ,we use Kadane's algo. But, here it is only positive elements).





#include<bits/stdc++.h>

using namespace std;
long long int A[100001];

int main()
{

      int t;
      cin>>t;
      while(t--)
      {

      long long int n,m,i,j,k,l,sum = 0 , ans = 0 ;
      cin>>n>>m;

        for(i=1;i<=n;i++)
        cin>>A[i];

        set<long long int> S ;
        S.insert(0) ;
        set<long long int>::iterator it ;

         for(i=1;i<=n;i++)
         {
            sum += A[i] ;
            sum %= m ;
            it = S.upper_bound(sum) ;
            if(it != S.end())
                ans = max(ans,sum-(*it)+m) ;
            else
                ans = max(ans,sum) ;
            S.insert(sum);
          }
          cout<<ans<<endl;

      }
  return 0;
}