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

C++ में कादाने एल्गोरिदम का कार्यान्वयन: अधिकतम सबएरे सम


कादाने एल्गोरिदम का उपयोग इंटीजर्स के ऐरे से अधिकतम सबएरे सम खोजने के लिए किया जाता है। यहां हम इस एल्गोरिदम को कार्यान्वित करने के लिए एक C++ प्रोग्राम पर चर्चा करेंगे।

एल्गोरिदम

Begin
    Function kadanes(int array[], int length):
        इनिशियलाइज़
        highestMax = 0
        currentElementMax = 0
        for i = 0 से length-1 तक
            currentElementMax = max(array[i], currentElementMax + array[i])
            highestMax = max(highestMax, currentElementMax)
        return highestMax
End

उदाहरण

#include <iostream>
using namespace std;

int kadanes(int array[], int length) {
    int highestMax = 0;
    int currentElementMax = 0;
    
    for(int i = 0; i < length; i++) {
        currentElementMax = max(array[i], currentElementMax + array[i]);
        highestMax = max(highestMax, currentElementMax);
    }
    return highestMax;
}

int main() {
    cout << "Enter the array length: ";
    int l;
    cin >> l;
    int arr[l];
    cout << "Enter the elements of array: ";
    for (int i = 0; i < l; i++) {
        cin >> arr[i];
    }
    cout << "The Maximum Sum is: " << kadanes(arr, l) << endl;
    return 0;
}

आउटपुट

Enter the array length: 7
Enter the elements of array: -1 -2 -3 -4 -5 6 7
The Maximum Sum is: 13

कादाने एल्गोरिदम O(n) समय में अधिकतम सबएरे सम खोजता है। यह नेगेटिव नंबर्स को हैंडल करता है वर्तमान मैक्स को रीसेट करके जब यह नेगेटिव हो जाता है। नोट: यदि सभी नंबर नेगेटिव हैं, तो यह एल्गोरिदम 0 लौटाता है (खाली सबएरे)। सभी नेगेटिव के लिए अधिकतम एलिमेंट लौटाने के लिए, highestMax को INT_MIN से इनिशियलाइज़ करें और currentElementMax को array[0] से।

  1. - C++ प्रोग्राम: हीप सॉर्ट लागू करना

    एक हीप एक पूर्ण बाइनरी ट्री है जो या तो मिन हीप या मैक्स हीप है। एक मैक्स हीप में, रूट पर कुंजी हीप में मौजूद सभी कुंजियों में अधिकतम होनी चाहिए। यह गुण उस बाइनरी ट्री में सभी नोड्स के लिए पुनरावर्ती रूप से सत्य होना चाहिए। मिन हीप मिनहीप के समान है। फंक्शन विवरण void BHeap::Insert(int ele): हीप मे

  1. - C++ प्रोग्राम: बबल सॉर्ट लागू करना

    बबल सॉर्ट तुलना-आधारित सॉर्टिंग एल्गोरिदम है। इस एल्गोरिदम में आसन्न तत्वों की तुलना की जाती है और सही क्रम बनाने के लिए स्वैप किया जाता है। यह एल्गोरिदम अन्य एल्गोरिदम की तुलना में सरल है, लेकिन इसकी कुछ कमियां भी हैं। यह एल्गोरिदम बड़ी संख्या में डेटा सेट के लिए उपयुक्त नहीं है। सॉर्टिंग कार्यों

  1. - C++ प्रोग्राम: रेडिक्स सॉर्ट लागू करना

    रेडिक्स सॉर्ट गैर-तुलनात्मक सॉर्टिंग एल्गोरिदम है। यह सॉर्टिंग एल्गोरिदम पूर्णांक कुंजियों पर काम करता है उन अंकों को समूहित करके जो समान स्थिति और मान साझा करते हैं। रेडिक्स एक संख्या प्रणाली का आधार है। जैसा कि हम जानते हैं कि दशमलव प्रणाली में रेडिक्स या आधार 10 है। इसलिए कुछ दशमलव संख्याओं को स