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

C++ में योग k से बड़ा वाला सबसे बड़ा सबअरे


इस ट्यूटोरियल में, हम एक प्रोग्राम लिखने जा रहे हैं जो योग k से बड़ा वाला सबसे बड़ा सबअरे ढूंढता है।

आइए समस्या को हल करने के चरण देखते हैं।

  • सरणी आरंभ करें।
  • सरणी पर पुनरावृति करें और प्रत्येक इंडेक्स पर योग को इंडेक्स के साथ एक वेक्टर में स्टोर करें।
  • उपरोक्त योगों को योग और इंडेक्स के आधार पर क्रमबद्ध करें।
  • इंडेक्स स्टोर करने के लिए एक सरणी आरंभ करें।
  • एक लूप लिखें जो n तक पुनरावृति करता है।
    • उपरोक्त इंडेक्स सरणी और पिछले योग सरणी इंडेक्स के न्यूनतम इंडेक्स के साथ मान अपडेट करें।
  • योग को 0 पर आरंभ करें।
  • एक लूप लिखें जो n तक पुनरावृति करता है।
    • वर्तमान तत्व को योग में जोड़ें।
    • यदि योग k से बड़ा है।
      • अधिकतम सबअरे लंबाई i + 1 है।
    • अन्यथा अधिकतम सबअरे लंबाई है
      • बाइनरी खोज का उपयोग करके पिछले योगों से इंडेक्स ढूंढें।
      • वह योग जो sum - k - 1 से कम है, वह तत्व इंडेक्स है जो हम चाहते हैं।

उदाहरण

आइए कोड देखते हैं।

#include <bits/stdc++.h> 
using namespace std; 

bool compare(const pair<int, int>& a, const pair<int, int>& b) { 
    if (a.first == b.first) { 
        return a.second < b.second; 
    } 
    return a.first < b.first; 
} 

int findIndex(vector<pair<int, int> >& previousSums, int n, int val) { 
    int start = 0; 
    int end = n - 1; 
    int mid, result = -1; 
    while (start <= end) { 
        mid = (start + end) / 2; 
        if (previousSums[mid].first <= val) { 
            result = mid; 
            start = mid + 1; 
        }else { 
            end = mid - 1; 
        } 
    } 
    return result; 
} 

int getLargestSubArray(int arr[], int n, int k) { 
    int maxLength = 0; 
    vector<pair<int, int> > previousSums; 
    int sum = 0, minIndexes[n]; 
    for (int i = 0; i < n; i++) { 
        sum = sum + arr[i]; 
        previousSums.push_back({ sum, i }); 
    } 
    sort(previousSums.begin(), previousSums.end(), compare); 
    minIndexes[0] = previousSums[0].second; 
    for (int i = 1; i < n; i++) { 
        minIndexes[i] = min(minIndexes[i - 1], previousSums[i].second); 
    } 
    sum = 0; 
    for (int i = 0; i < n; i++) { 
        sum = sum + arr[i]; 
        if (sum > k) { 
            maxLength = i + 1; 
        }else { 
            int ind = findIndex(previousSums, n, sum - k - 1); 
            if (ind != -1 && minIndexes[ind] < i) { 
                maxLength = max(maxLength, i - minIndexes[ind]); 
            } 
        } 
    } 
    return maxLength; 
} 

int main() { 
    int arr[] = { 5, 3, -3, 2, 4, 7 }; 
    int k = 5, n = 6; 
    cout << getLargestSubArray(arr, n, k) << endl; 
    return 0; 
}

आउटपुट

यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्नलिखित परिणाम मिलेगा।

6

निष्कर्ष

यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उन्हें टिप्पणी अनुभाग में उल्लेख करें।


  1. - C++ में दिए गए योग से कम या बराबर अधिकतम योग वाली उपसरणी (Maximum sum subarray having sum less than or equal to given sum)

    इस समस्या में, हमें एक सरणी और एक योग दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में दिए गए योग से कम या बराबर योग वाली अधिकतम योग उपसरणी ढूंढे। हमें किसी भी लंबाई की उपसरणी ढूंढनी है जिसका योग दिए गए योग से कम या बराबर हो। आइए एक उदाहरण से समझते हैं: इनपुट - सरणी = {3, 5, 1, 8, 2, 9}, य

  1. - C++ में अधिकतम उपसरणी योग मॉड्यूलो m (Maximum subarray sum modulo m)

    इस समस्या में, हमें आकार n की एक सरणी और एक पूर्णांक m दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में अधिकतम उपसरणी योग मॉड्यूलो m ढूंढे। प्रोग्राम विवरण - यहां, हम उपसरणी के सभी तत्वों के योग को m से विभाजित करके प्राप्त अधिकतम मान ढूंढेंगे। आइए एक उदाहरण से समझते हैं: इनपुट - सरणी = {4

  1. - C++ में प्रीफिक्स सम का उपयोग करके O(n) में अधिकतम सबएरे सम

    समस्या कथनसकारात्मक और नकारात्मक पूर्णांकों का एक सरणी दिया गया है, उस सरणी में अधिकतम सबएरे सम ज्ञात करें।उदाहरणयदि इनपुट सरणी है {-12, -5, 4, -1, -7, 1, 8, -3} तो आउटपुट 9 होगा।एल्गोरिदमइनपुट सरणी का प्रीफिक्स सम निकालें।प्रारंभ करें: min_prefix_sum = 0, res = -infinitei = 0 से n तक लूप बनाए रखें