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

C++ में दो ट्रैवर्सल का उपयोग करके अधिकतम गुणनफल सबअरे


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

समस्या विवरण - यहां सरणी में, हम दो ट्रैवर्सल का उपयोग करके अधिकतम गुणनफल सबअरे ढूंढेंगे: एक इंडेक्स 0 से और दूसरा इंडेक्स (n-1) से।

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

इनपुट

arr[] = {4, -2, 5, -6, 0, 8}

आउटपुट

240

उदाहरण

Subarray = {4, -2, 5, -6} Maximum product = 4 * (-2) * 5 * (-6) = 240

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

दो ट्रैवर्सल का उपयोग करके इस समस्या को हल करने के लिए। यहां, हम बाएं से दाएं ट्रैवर्सल यानी इंडेक्स 0 से n-1 के लिए दो स्थानीय अधिकतम मानों का उपयोग करके अधिकतम गुणनफल ढूंढेंगे। और एक दाएं से बाएं ट्रैवर्सल यानी इंडेक्स n-1 से 0 के लिए। बाकी एल्गोरिदम अधिकतम गुणनफल सबअरे खोजने जैसा ही है।

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

उदाहरण

#include<iostream> 
using namespace std; 
int CalcMaxProductSubArray(int arr[], int n) { 
    int frntMax = 1, rearMax = 1, maxVal = 1; 
    for (int i=0; i<n; i++) { 
        frntMax = frntMax*arr[i]; 
        if (frntMax == 0) 
            frntMax = 1; 
    } 
    for (int i=n-1; i>=0; i--) { 
        rearMax = rearMax * arr[i]; 
        if (rearMax == 0) 
            rearMax = 1; 
    } 
    maxVal = max(frntMax, rearMax); 
    return maxVal; 
} 
int main() { 
    int arr[] = {4, -2, 5, -6, 0, 8}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout<<"Maximum product subarray is "<<CalcMaxProductSubArray(arr, n); 
    return 0; 
}

आउटपुट

Maximum product subarray is 240
  1. C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल

    इस समस्या में, हमें n नोड्स के साथ एक अविभाजित कनेक्टेड ट्री T दिया गया है। हमारा कार्य C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल ढूंढने के लिए एक प्रोग्राम बनाना है। समस्या विवरण - ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल ढूंढने के लिए। हम सभी गैर-प्रतिच्छेदी पथ ढूंढेंगे औ

  1. - C++ में LCM उत्पाद के बराबर होने वाले अधिकतम लंबाई के सबएरे

    मान लीजिए हमारे पास एक सरणी A है। हमें सबएरे की अधिकतम लंबाई ढूंढनी है, जिसका LCM उस सबएरे के एलिमेंट्स के उत्पाद के समान है। यदि ऐसा सबएरे नहीं मिलता, तो -1 वापस करें। मान लीजिए सरणी {6, 10, 21} है, तो लंबाई 2 है, क्योंकि सबएरे {10, 21} है, जिसका LCM 210 है, और उत्पाद भी 210 है। दृष्टिकोण सीधा है।

  1. - C++ STL का उपयोग करके ऐरे का गुणनफल

    यह ऐरे गुणनफल ज्ञात करने के लिए C++ प्रोग्राम का एक उदाहरण है। एल्गोरिदम Begin ऐरे के मान इनिशियलाइज़ करें। ऐरे का गुणनफल लौटाने के लिए उपयोगकर्ता परिभाषित फंक्शन accumulate को कॉल करें। समाधान प्रिंट करें। End. उदाहरण कोड #include <iostream> #include <numeric> using names