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

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


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

हमें किसी भी लंबाई की उपसरणी ढूंढनी है जिसका योग दिए गए योग से कम या बराबर हो।

आइए एक उदाहरण से समझते हैं:

इनपुट - सरणी = {3, 5, 1, 8, 2, 9}, योग = 25

आउटपुट - 25

व्याख्या - योग 25 से कम या बराबर वाली उपसरणियां हैं {5, 1, 8, 2, 9}

अधिकतम योग उपसरणी ढूंढने की एक सरल विधि सरणी पर पुनरावृति करना और सभी उपसरणियों का योग ढूंढना और फिर निकटतम या बराबर योग ढूंढना है। लेकिन इस विधि की समय जटिलता O(n²) होगी क्योंकि दो लूप आवश्यक हैं।

इस समस्या को हल करने की एक अधिक कुशल विधि स्लाइडिंग विंडो (sliding window) विधि है। जिसमें हम वर्तमान योग की तुलना अधिकतम योग से करेंगे और तुलना के आधार पर विंडो में तत्व जोड़ेंगे या घटाएंगे।

उदाहरण

#include <iostream>
using namespace std;

int findMax(int a, int b){
    if(a > b) return a;
    return b;
}

int maxSumsubarray(int arr[], int n, int maxSum){
    int sum = arr[0], overallMax = 0, start = 0;
    for (int i = 1; i < n; i++) {
        if (sum <= maxSum)
            overallMax = findMax(overallMax, sum);
        while (sum + arr[i] > maxSum && start < i) {
            sum -= arr[start];
            start++;
        }
        sum += arr[i];
    }
    if (sum <= maxSum)
        overallMax = findMax(overallMax, sum);
    return overallMax;
}

int main(){
    int arr[] = {3, 1, 4, 7, 2, 9, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 20;
    cout << "अधिकतम योग वाली उपसरणी जिसका योग " << sum << " से कम या बराबर है: " << maxSumsubarray(arr, n, sum);
    return 0;
}

आउटपुट

अधिकतम योग वाली उपसरणी जिसका योग 20 से कम या बराबर है: 18
  1. - C++ में अधिकतम उपसरणी योग मॉड्यूलो m (Maximum subarray sum modulo m)

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

  1. - C++ में दी गई सरणी को k बार दोहराकर बनी सरणी में अधिकतम सबएरे सम

    इस समस्या में, हमें एक सरणी और एक संख्या k दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो दी गई सरणी को k बार दोहराकर बनी सरणी में अधिकतम सबएरे सम ढूंढेगा।समस्या विवरण - यहां, हम दी गई सरणी को k बार दोहराकर बनी सरणी से बने सबएरे का अधिकतम सम ज्ञात करेंगे।समस्या को समझने के लिए एक उदाहरण लेते हैं,इनप

  1. - C++ में दिए गए N के बराबर योग वाली अधिकतम अभाज्य संख्याएं

    इस समस्या में, हमें एक संख्या n दी गई है। हमारा कार्य उन अधिकतम अभाज्य संख्याओं की गिनती ढूंढना है जिनका योग दिए गए N के बराबर हो।यहां, हम अधिकतम अभाज्य संख्याएं ढूंढेंगे जिन्हें जोड़ने पर वह संख्या के बराबर होंगी।अभाज्य संख्याएं वे संख्याएं हैं जिन्हें केवल स्वयं या एक से विभाजित किया जा सकता है।आइ