Maximum Subarray Sum

Maximum Subarray Sum

题意

给你一个大小为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 <bits/stdc++.h>

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<ll> st;

        ll mx = 0;

        for(int i = 0; i < n; i++)

        {

            set<ll>::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;

}