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

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


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

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

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

इनपुट

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

आउटपुट

30

व्याख्या

बाईटॉनिक सबअरे है [2, 3, 7, 9, 6, 3]। योग = 2 + 3 + 7 + 9 + 6 + 3 = 30

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

समाधान बाईटॉनिक सबसीक्वेंस समस्या के समान है। हम दो सरणियाँ incSubArr[] और decSubArr[] बनाएंगे। जो बढ़ते और घटते सबअरे को संग्रहीत करेंगे। इंडेक्स i पर, incSubArr[i] 0 से i तक बढ़ता हुआ सबअरे ढूंढेगा। और decSubArr[i] i से N तक बढ़ता हुआ सबअरे ढूंढेगा।

maxSum अधिकतम मान है जिसकी गणना (incSubArr[i] + decSubArr[i] - arr[i]) के रूप में की जाती है।

उदाहरण

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

#include <iostream> 
using namespace std; 
int findMaxSumBiTonicSubArr(int arr[], int N){ 
    int incSubArr[N], decSubArr[N]; 
    int max_sum = -1; 
    incSubArr[0] = arr[0]; 
    for (int i=1; i<N; i++) 
        if (arr[i] > arr[i-1]) 
            incSubArr[i] = incSubArr[i-1] + arr[i]; 
        else 
            incSubArr[i] = arr[i]; 
    decSubArr[N-1] = arr[N-1]; 
    for (int i= (N-2); i>=0; i--) 
        if (arr[i] > arr[i+1]) 
            decSubArr[i] = decSubArr[i+1] + arr[i]; 
        else 
            decSubArr[i] = arr[i]; 
    for (int i=0; i<N; i++) 
        if(max_sum < (incSubArr[i] + decSubArr[i] - arr[i])) max_sum = incSubArr[i] + decSubArr[i] - arr[i]; 
    return max_sum; 
} 
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 Bitonic Subarray is "<<findMaxSumBiTonicSubArr(arr, N); 
    return 0; 
}

आउटपुट

The Maximum Sum of Bitonic Subarray is 30
  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} का योग है।हम इस समस्या को डिवाइड एंड कंकर विधि का उपयोग करके हल