C++ में बाइनरी सर्च दृष्टिकोण का उपयोग करके अधिकतम सबएरे योग ज्ञात करना

बाइनरी सर्च एक तेज खोज एल्गोरिदम है जिसकी रन-टाइम जटिलता O(log n) है। यह एल्गोरिदम विभाजन और विजय के सिद्धांत पर काम करता है। इस एल्गोरिदम के ठीक से काम करने के लिए, डेटा संग्रह सॉर्टेड रूप में होना चाहिए।

बाइनरी सर्च संग्रह के मध्य तत्व की तुलना करके किसी विशेष आइटम को खोजता है। यदि मेल होता है, तो आइटम का इंडेक्स लौटाया जाता है। यदि मध्य आइटम आइटम से बड़ा है, तो आइटम को मध्य आइटम के बाईं ओर सब-ऐरे में खोजा जाता है। अन्यथा, आइटम को मध्य आइटम के दाईं ओर सब-ऐरे में खोजा जाता है। यह प्रक्रिया सब-ऐरे पर भी तब तक जारी रहती है जब तक सबएरे का आकार शून्य नहीं हो जाता।

यह बाइनरी सर्च दृष्टिकोण का उपयोग करके अधिकतम सबएरे योग ज्ञात करने का प्रोग्राम है।

एल्गोरिदम

Begin
    दो इंटीजर्स का अधिकतम खोजने के लिए maximum() इंटीजर फंक्शन घोषित करें
    val1, val2 को इंटीजर डेटाटाइप के रूप में घोषित करें
    उन्हें पैरामीटर के रूप में पास करें
    val1 और val2 के बीच अधिकतम जांचें
    अधिकतम मान लौटाएं
End

Begin
    MCS() इंटीजर फंक्शन घोषित करें जो सब-ऐरे के मध्य को शामिल करने वाला अधिकतम योग सब-ऐरे खोजे
    array[] ऐरे और वेरिएबल l, m, h को इंटीजर डेटाटाइप के रूप में घोषित करें
    उन्हें पैरामीटर के रूप में पास करें
    वेरिएबल s, sum_of_left_part को इंटीजर डेटाटाइप के रूप में घोषित करें
        s = 0 इनिशियलाइज़ करें
        sum_of_left_part = -1 इनिशियलाइज़ करें
    for (int i = m; i >= l; i--)
        s = s + array[i]
    if (s > sum_of_left_part) then
        sum_of_left_part = s
        s = 0
    sum_of_right_part वेरिएबल को इंटीजर डेटाटाइप के रूप में घोषित करें
        sum_of_right_part = -1 इनिशियलाइज़ करें
    for (int i = m+1; i <= h; i++)
        s = s + array[i]
    if (s > sum_of_right_part) then
        sum_of_right_part = s
    return sum_of_left_part + sum_of_right_part
End

Begin
    MaximumSum_of_SubArray() इंटीजर फंक्शन घोषित करें
    array[] ऐरे और वेरिएबल l, h को इंटीजर डेटाटाइप के रूप में घोषित करें
        उन्हें पैरामीटर के रूप में पास करें
    m को इंटीजर डेटाटाइप के रूप में घोषित करें
    if (l == h) then
        return array[l]
    m = (l + h) / 2
    return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h))
    
    number_of_elements और i को इंटीजर डेटाटाइप के रूप में घोषित करें
    "Enter the number of elements of array: " प्रिंट करें
    number_of_elements का मान दर्ज करें
    a[number_of_elements] ऐरे को इंटीजर डेटाटाइप के रूप में घोषित करें
    for(i = 0; i < n; i++)
        "Enter the element of" प्रिंट करें
        ऐरे का डेटा तत्व दर्ज करें
    "Maximum sum of Sub-Array is: " प्रिंट करें
        MaximumSum_of_SubArray(a, 0, n-1) का परिणाम प्रिंट करें
End

उदाहरण

#include <iostream>
using namespace std;

int maximum(int val1, int val2) { // दो इंटीजर्स का अधिकतम खोजें
    return (val1 > val2) ? val1 : val2;
}

int MCS(int array[], int l, int m, int h) { // सब-ऐरे के मध्य को शामिल करने वाला अधिकतम योग सब-ऐरे खोजें
    int s = 0;
    int sum_of_left_part = -1;
    for (int i = m; i >= l; i--) {
        s = s + array[i];
        if (s > sum_of_left_part)
            sum_of_left_part = s;
    }
    s = 0;
    int sum_of_right_part = -1;
    for (int i = m+1; i <= h; i++) {
        s = s + array[i];
        if (s > sum_of_right_part)
            sum_of_right_part = s;
    }
    return sum_of_left_part + sum_of_right_part; // मध्य के बाएं और दाएं तत्वों का योग लौटाएं
}

int MaximumSum_of_SubArray(int array[], int l, int h) {
    int m;
    if (l == h)
        return array[l];
    m = (l + h) / 2;
    return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h));
}

int main() {
    int number_of_elements, i;
    cout << "Enter the number of elements of array: ";
    cin >> number_of_elements;
    cout << endl;
    int a[number_of_elements];
    for (i = 0; i < number_of_elements; i++) {
        cout << "Enter the element of " << i+1 << ": ";
        cin >> a[i];
    }
    cout << "\nMaximum sum of Sub-Array is: " << MaximumSum_of_SubArray(a, 0, number_of_elements - 1);
    return 0;
}

आउटपुट

Enter the number of elements of array: 5
Enter the element of 1: 12
Enter the element of 2: 45
Enter the element of 3: 56
Enter the element of 4: 48
Enter the element of 5: 75
Maximum sum of Sub-Array is: 236