कैडेंस का एल्गोरिथ्म: सबसे बड़ा योग सन्निहित उपसरणी

सबसे बड़ा योग वाला सन्निहित उप-सरण कौन सा है?

उपसरणी सरणी का एक सतत भाग है। यह सरणी का एक एकल तत्व या सरणी का कुछ अंश हो सकता है। सबसे बड़ा योग सन्निहित उपसरणी का अर्थ है वह उपसरणी जिसका योग मान अधिकतम है।

उदाहरण के लिए, {-10, 5, 1, 6, -9, 2, -7, 3, -5} नामक एरे को लें। इसके सबएरे {-10, 5, 1, 6}, {5, 1, 6} या {2, -7, 3, -5} आदि हो सकते हैं। हालांकि, {5, 1, 6, 3} एक सबएरे नहीं हो सकता क्योंकि इसके तत्व एक सन्निहित क्रम में नहीं हैं।

यदि आप ध्यान दें, तो सभी उप-सरणियों में से, हाइलाइट की गई उप-सरणी {5, 1, 6} का योग मान अधिकतम है:

उप-सरण {5, 1, 6} का योग 12 है, जो उपरोक्त सारणी के सभी संभावित उप-सरणों का अधिकतम योग है। अतः, इस सारणी के लिए, अधिकतम योग वाला सन्निहित उप-सरण {5, 1, 6} है।

सबसे बड़े योग वाले सन्निहित उप-सरण को हल करने का सरल तरीका

इस समस्या को हल करने का सरल तरीका यह है कि दो लूपों का उपयोग करके सभी उप-सरणी ज्ञात करें, योग की गणना करें, और फिर उसका अधिकतम मान ज्ञात करें।

सबसे बड़े योग वाले सन्निहित उप-सरणों को खोजने के सरल तरीके का फ्लोचार्ट यहाँ दिया गया है। यह एक ब्रूट-फोर्स विधि है, क्योंकि हम प्रत्येक संभव उप-सरणों से गुजरते हैं।

ऐसा करने के लिए सरल चरण यहां दिए गए हैं।

चरण 1) हस्ताक्षर करना अधिकतम योग न्यूनतम पूर्णांक मान के साथ और सेट करें शुरू करना और समाप्त शून्य करने के लिए।

चरण 2) चलो i और j वे सरणी सूचकांक हैं जहाँ j से अधिक या बराबर है i; i सबएरे की शुरुआत को चिह्नित करता है और j यह खत्म होता है।

चरण 3) वर्तमान_योग इसमें चालू योग रहता है। प्रत्येक अपडेट के बाद, जांचें कि क्या वर्तमान_योग से अधिक है अधिकतम योग.

चरण 4) If वर्तमान_योग अगर बड़ा है, तो बदलें अधिकतम योग इसके साथ.

चरण 5) . j ऐरे के अंत तक पहुँचने पर, वृद्धि करें i और रीसेट करें वर्तमान_योग 0 लिए.

चरण 6) दोहराओ जब तक i ऐरे के अंत तक पहुँच जाता है। अधिकतम योग फिर इसमें सबसे बड़ा सबएरे योग होता है।

उपनाम Code सरल दृष्टिकोण के लिए

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ सरल दृष्टिकोण का कार्यान्वयन

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

आउटपुट:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python सरल दृष्टिकोण का कार्यान्वयन

def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)

आउटपुट:

largest sum is 12
largest sum contiguous subarray: 5      1       6

सबसे बड़े योग वाले सन्निहित उप-सरण को खोजने के लिए कडेन का एल्गोरिदम

कडेन का एल्गोरिदम एक डायनामिक प्रोग्रामिंग विधि है जो दो लूप के बजाय एक ही लूप का उपयोग करती है। यह मिश्रित धनात्मक और ऋणात्मक संख्याओं वाले सरणियों को संभालता है, बशर्ते कि कम से कम एक मान गैर-ऋणात्मक हो।

सबसे बड़े योग वाले सन्निहित उप-सरण को खोजने के लिए हमें केवल दो चरों की आवश्यकता होती है। यहाँ फ्लोचार्ट दिया गया है:

कडाने के एल्गोरिथ्म के चरण इस प्रकार हैं:

चरण 1) दो वेरिएबल बनाएं, वर्तमान_योग और अधिकतम योग.

वर्तमान_योग यह किसी विशिष्ट ऐरे इंडेक्स पर समाप्त होने वाले अधिकतम योग को रखता है, जबकि अधिकतम योग इसमें अब तक देखे गए सबसे बड़े योग मान को संग्रहित किया गया है।

चरण 2) प्रत्येक ऐरे एलिमेंट को जोड़ें वर्तमान_योगफिर नीचे दी गई दो शर्तों की जांच करें:

• If वर्तमान_योग यदि यह वर्तमान तत्व से कम है, तो वर्तमान_योग वर्तमान तत्व बन जाता है।
• If अधिकतम योग से कम है वर्तमान_योग, तो अधिकतम योग हो जाता है वर्तमान_योग.

चरण 3) संपूर्ण ऐरे के लिए पिछले चरण को दोहराने के बाद, अधिकतम योग इसमें सबसे बड़ा योग वाला सन्निहित उप-सरण शामिल है।

कडाने के एल्गोरिथ्म का उदाहरण

हम एक छोटे से ऐरे पर कडेन के एल्गोरिदम का प्रदर्शन करते हैं और सबसे बड़े योग वाले सन्निहित सबऐरे को खोजने के प्रत्येक चरण को समझाते हैं।

मान लीजिए कि दिया गया ऐरे निम्नलिखित प्रकार का है:

कडेन के एल्गोरिदम के चरण इस प्रकार हैं:

चरण 1) दो वेरिएबल बनाएं, वर्तमान_योग और अधिकतम योगINT_MIN को असाइन करें अधिकतम योग और शून्य से वर्तमान_योगयहां, INT_MIN न्यूनतम पूर्णांक मान को दर्शाता है।

चरण 2) सूचकांक 0 पर मान 4 है। इसलिए, वर्तमान_योग = 0 + 4 = 4. चूंकि वर्तमान_योग से बड़ा है अधिकतम योग, अधिकतम योग 4 हो जाता है.

चरण 3) सूचकांक 1 पर मान -2 है। इसलिए, वर्तमान_योग = 4 + (-2) = 2.

इस समय वर्तमान_योग से कम है अधिकतम योगपरिणामस्वरूप, मूल्य अधिकतम योग अपडेट नहीं किया गया है।

चरण 4) अगला मान 1 है। इसे जोड़ने पर वर्तमान_योग 3 देता है। चूंकि अधिकतम योग (4) अभी भी इससे अधिक है वर्तमान_योग, अधिकतम योग अपडेट नहीं किया गया है।

चरण 5) इंडेक्स 3 पर मान 3 है। वृद्धि हो रही है। वर्तमान_योग 3 से भाग देने पर वर्तमान_योग = 6.

इस मामले में, अधिकतम योग की तुलना में छोटा है वर्तमान_योग, इतना अधिकतम योग को मान के साथ अपडेट किया जाता है वर्तमान_योग.

चरण 6) ऐरे के अंतिम तत्व के लिए, हमारे पास -1 है। इसे जोड़ने पर वर्तमान_योग 5 देता है, जो इससे छोटा है अधिकतम योग। इसलिए, अधिकतम योग 6 रहता है।

जैसे ही हम ऐरे के अंत तक पहुँचते हैं, एल्गोरिदम यहीं समाप्त हो जाता है। अब, अधिकतम योग इसमें अधिकतम योग है, जो कि 6 है। उप-सरण {4, -2, 1, 3} है।

उपनाम Code कडेन के एल्गोरिदम के लिए

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++ कडाने के एल्गोरिदम का कार्यान्वयन

#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}

आउटपुट:

largest sum is 12

Python कडाने के एल्गोरिदम का कार्यान्वयन

def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])

आउटपुट:

largest sum is 12

सबसे बड़े योग सन्निहित उपसरणी के लिए जटिलता विश्लेषण

सरल विधि में दो लूप का उपयोग करके सभी संभावित सबएरे के योग की गणना की जाती है और सबसे बड़े योग का पता लगाया जाता है। यह एक ब्रूट-फोर्स विधि है; प्रत्येक लूप अंत तक चलता है। सरणी, दे रहा है O(N²) समय है.

कडेन का एल्गोरिदम केवल एक लूप का उपयोग करता है, जिससे O(N) समय और O(1) अतिरिक्त स्थान प्राप्त होता है। 100 तत्वों वाले एक ऐरे पर, सरल विधि 100 × 100 = 10,000 ऑपरेशन करती है, जबकि कडेन का एल्गोरिदम केवल 100 ऑपरेशन करता है - बड़े इनपुट के लिए यह गति में एक उल्लेखनीय वृद्धि है।

अक्सर पूछे जाने वाले प्रश्न