Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में अधिकतम उपसरणी योग मॉड्यूलो m (Maximum subarray sum modulo 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

इस समस्या को हल करने के लिए, हम प्रीफिक्ससममॉड्यूलो सरणी (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
  1. - C++ में ऐरे में अधिकतम संतुलन योग

    समस्या कथन एक ऐरे arr[] दिया गया है। इंडेक्स i के लिए arr[] में अधिकतम प्रीफिक्स योग का मान ढूंढें जो सफिक्स योग भी हो। उदाहरण यदि इनपुट ऐरे है - Arr[] = {1, 2, 3, 5, 3, 2, 1} तो आउटपुट 11 है - प्रीफिक्स योग = arr[0..3] = 1 + 2 + 3 + 5 = 11 और सफिक्स योग = arr[3..6] = 5 + 3 + 2 + 1 = 11 एल्गोरिदम

  1. - सख्ती से बढ़ते सब-अर्रे का अधिकतम योग खोजें C++ में

    मान लीजिए हमारे पास n पूर्णांकों का एक ऐरे है। सख्ती से बढ़ते सब-अर्रे का अधिकतम योग खोजें। तो यदि ऐरे [1, 2, 3, 2, 5, 1, 7] जैसा है, तो योग 8 होगा। इस ऐरे में तीन सख्ती से बढ़ते सब-अर्रे हैं ये हैं {1, 2, 3}, {2, 5} और {1, 7}। अधिकतम योग वाला सब-अर्रे {1, 7} है। इस समस्या को हल करने के लिए, हमें अध

  1. - C++ में डिवाइड एंड कंकर का उपयोग करके अधिकतम योग सबएरे

    मान लीजिए हमारे पास धनात्मक और ऋणात्मक मानों के साथ डेटा की एक सूची है। हमें सन्निहित सबएरे का योग ढूंढना है जिसका योग सबसे बड़ा है। मान लीजिए सूची में {-2, -5, 6, -2, -3, 1, 5, -6} है, तो अधिकतम सबएरे का योग 7 है। यह {6, -2, -3, 1, 5} का योग है।हम इस समस्या को डिवाइड एंड कंकर विधि का उपयोग करके हल