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

C++ में अधिकतम योग बाई-टॉनिक सबसीक्वेंस


इस समस्या में, हमें एक सरणी arr[] दी गई है। हमारा कार्य C++ में अधिकतम योग बाई-टॉनिक सबसीक्वेंस ढूंढने के लिए एक प्रोग्राम बनाना है।

बाई-टॉनिक सबसीक्वेंस एक विशेष क्रम है जिसके तत्व पहले बढ़ते हैं और फिर घटते हैं।

आइए एक उदाहरण से समस्या को समझते हैं,

इनपुट

arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1}

आउटपुट

33

व्याख्या

बाई-टॉनिक सबसीक्वेंस जो सबसे बड़ा योग देता है वह है {2, 3, 7, 9, 6, 5, 1} योग = 2 + 3 + 7 + 9 + 6 + 5 + 1 = 33

समाधान दृष्टिकोण

अधिकतम योग बाईटॉनिक सबसीक्वेंस खोजने के लिए, हम दो सरणियाँ, incSeq[] और decSeq[] इस तरह बनाएंगे कि इंडेक्स पर एक तत्व i के लिए, incSeq[i] में arr[0...i] से सख्ती से बढ़ते सभी तत्वों का योग हो और decSeq[i] में arr[i...n] से सख्ती से घटते सभी तत्वों का योग हो।

अंत में, हम (incSeq[i] + decSeq[i] - arr[i]) से अधिकतम मान के रूप में maxSum वापस करेंगे।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

#include <iostream> 
using namespace std; 
int calcMaxVal(int a, int b){ 
    if(a > b) 
        return a; 
    return b; 
} 
int findMaxSumBiTonicSubSeq(int arr[], int N){ 
    int maxSum = -1; 
    int incSeq[N], decSeq[N]; 
    for (int i = 0; i < N; i++){ 
        decSeq[i] = arr[i]; 
        incSeq[i] = arr[i]; 
    } 
    for (int i = 1; i < N; i++) 
        for (int j = 0; j < i; j++) 
            if (arr[i] > arr[j] && incSeq[i] < incSeq[j] + arr[i]) incSeq[i] = incSeq[j] + arr[i]; 
    for (int i = N - 2; i >= 0; i--) 
        for (int j = N - 1; j > i; j--) 
            if (arr[i] > arr[j] && decSeq[i] < decSeq[j] + arr[i]) 
                decSeq[i] = decSeq[j] + arr[i]; 
    for (int i = 0; i < N; i++) 
        maxSum = calcMaxVal(maxSum, (decSeq[i] + incSeq[i] - arr[i])); 
    return maxSum; 
} 
int main(){ 
    int arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1}; 
    int N = sizeof(arr) / sizeof(arr[0]); 
    cout<<"The Maximum Sum of Bi-tonic subsequence is : "<<findMaxSumBiTonicSubSeq(arr, N); 
    return 0; 
}

आउटपुट

The Maximum Sum of Bi-tonic subsequence is : 33
  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 तक लूप बनाए रखें

  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 एल्गोरिदम