सी++ में अधिकतम सबरे योग मॉड्यूलो एम

इस समस्या में, हमें n आकार की एक सरणी और एक पूर्णांक m दिया जाता है। हमारा काम एक ऐसा प्रोग्राम बनाना है जो C++ में अधिकतम सबअरे योग मॉड्यूल m ढूंढेगा।

कार्यक्रम विवरण - यहां, हम सबएरे के सभी तत्वों के योग को m से विभाजित करके प्राप्त अधिकतम मान प्राप्त करेंगे।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट - सरणी ={4, 9 ,2} मीटर =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 =(prefixi + prefixj + 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<<"Maximum subarray sum modulo "<<m<<" is "<<calcMaxSum(arr, n, m) < endl;
   return 0;
}

आउटपुट

Maximum subarray sum modulo 5 is 4