Problem 22: Maximum Subarray Sum Modulo
Problem Statement: Given an array of n integers and an integer m, find the maximum value of the sum of a subarray modulo m.
Input
The first line contains two integers n and m. The second line contains n spaceāseparated integers.
Output
Print the maximum subarray sum modulo m.
Examples
Input:
3 7
3 3 9
Output:
6
Solution Explanation
Method 1: Use prefix sums with a set to store previous prefix sums and for each prefix, find the smallest prefix greater than the current prefix to maximize the modulo difference. Method 2: Use a brute force approach by checking all subarrays which works for small arrays but is not efficient.
Solution in C++
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m; cin >> n >> m;
vector a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
set prefixSet;
long long ans = 0, prefix = 0;
prefixSet.insert(0);
for (int i = 0; i < n; i++){
prefix = (prefix + a[i]) % m;
ans = max(ans, prefix);
auto it = prefixSet.lower_bound(prefix + 1);
if(it != prefixSet.end()){
ans = max(ans, (prefix - *it + m) % m);
}
prefixSet.insert(prefix);
}
cout << ans << "
";
return 0;
}