इस समस्या में, हमें आकार 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
इस समस्या को हल करने के लिए, हम प्रीफिक्ससममॉड्यूलो सरणी (prefixSumModulo Array) की गणना करते हैं। और सूत्र का उपयोग करके प्रत्येक इंडेक्स के लिए maxSum की गणना करते हैं: i पर maxSum = (prefix_i + prefix_j + m) % m
उदाहरण
#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 << "अधिकतम उपसरणी योग मॉड्यूलो " << m << " है " << calcMaxSum(arr, n, m) << endl;
return 0;
}
आउटपुट
अधिकतम उपसरणी योग मॉड्यूलो 5 है 4