C ++中的最大子数组总和模m
在这个问题中，我们得到了一个大小为n和整数m的数组。我们的任务是创建一个程序，该程序将在C++中找到最大子模和m。
程序说明-在这里，我们将找到通过将子数组所有元素的总和除以m获得的最大值。
让我们举个例子来了解这个问题，
输入-数组={4，9，2}m=6
输出-5
说明-所有子数组及其除法运算的余数
{4}: 4%6 = 4
{9}: 9%6 = 3
{2}: 2%6 = 2
{4, 9}: 13%6 = 1
{9, 2}: 11%6 = 5
{4, 9, 2}: 15%6 = 3为了解决这个问题，我们计算了prefixSumModuloArray。并使用公式计算每个索引的maxSum，即i=（prefixi+prefixj+m）％m时的maxSum
示例
程序来说明我们的解决方案，
#include<bits/stdc++.h>
using namespace std;
int calcMaxSum(int arr[], int n, int m) {
int x, prefix = 0, maxSumMod = 0;
set<int> sums;
sums.insert(0);
for (int i = 0; i < n; i++){
prefix = (prefix + arr[i])%m;
maxSumMod = max(maxSumMod, prefix);
auto it = sums.lower_bound(prefix+1);
if (it != sums.end())
maxSumMod = max(maxSumMod, prefix - (*it) + m );
sums.insert(prefix);
}
return maxSumMod;
}
int main() {
int arr[] = {4, 9, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int m = 5;
cout<<"Maximum subarray sum modulo "<<m<<" is "<<calcMaxSum(arr, n, m) < endl;
return 0;
}输出结果
Maximum subarray sum modulo 5 is 4