题意

给你一个大小为N的数组和另外一个整数M。你的目标是找到每个子数组的和对M取余数的最大值。子数组是指原数组的任意连续元素的子集。

分析

求出前缀和，问题变成了O(n*n)复杂度的问题，但是仍然不能解决问题。

设prefix为前缀和，设i < j，一般都是通过算sum = prefix[j] - prefix[i]求和的最大值，但是本题中有取模，要求sum最大。

第一种情况：如果prefix[j] > prefix[i]，sum < prefix[j]，这种情况就不需要考虑了。

第二种情况：prefix[j] < prefix[i]，又i < j，那么prefix[j]是取模后得到的值，此时sum = prefix[j] + m - prefix[i]，要sum尽可能的大，则要求prefix[i]尽可能的小，而prefix[i] > prefix[j]，所以每次要

前面出现过的前缀和里找比它大一点的值，这里就想到了C++里的set，有序的集合，set.upper_bound二分查找，并插入前缀和，复杂度O(nlogn)。

code

#include 
    
     using namespace std;typedef long long ll;const int MAXN = 1e5 + 5;ll a[MAXN];int main(){    ios::sync_with_stdio(0);    cin.tie(0);    int T, n;    ll m;    cin >> T;    while(T--)    {        cin >> n >> m;        for(int i = 0; i < n; i++)        {            ll x;            cin >> x;            if(i == 0) a[0] = x % m;            else a[i] = (a[i - 1] % m + x) % m;        }        set
     
       st;        ll mx = 0;        for(int i = 0; i < n; i++)        {            set
      
       ::iterator x = st.upper_bound(a[i]);            if(x != st.end()) mx = max(mx, a[i] + m - *x);            mx = max(mx, a[i]);            st.insert(a[i]);        }        cout << mx << endl;    }    return 0;}