कैडेंस का एल्गोरिथ्म: सबसे बड़ा योग सन्निहित उपसरणी
सबसे बड़ा योग सन्निहित उपसरणी क्या है?
उपसरणी सरणी का एक सतत भाग है। यह सरणी का एक एकल तत्व या सरणी का कुछ अंश हो सकता है। सबसे बड़ा योग सन्निहित उपसरणी का अर्थ है वह उपसरणी जिसका योग मान अधिकतम है।
उदाहरण के लिए, एक सरणी {-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} = 11 का योग, उपरोक्त सारणी के उपसरणी के सभी संभावित संयोजनों में अधिकतम योग है। इसलिए, उपरोक्त सारणी के लिए, अधिकतम उपसरणी {5,1,6} है।
कैडेंस का एल्गोरिथ्म: सबसे बड़ा योग सन्निहित उपसरणी
सबसे बड़े योग सन्निहित उपसरणी को हल करने का सरल तरीका
इस समस्या को हल करने का सरल तरीका यह है कि दो लूपों का उपयोग करके सभी उप-सरणी ज्ञात करें, योग की गणना करें, और फिर उसका अधिकतम मान ज्ञात करें।
यहाँ सबसे बड़ी राशि वाले सन्निहित उप-सरणी को खोजने के सरल दृष्टिकोण के लिए फ़्लोचार्ट दिया गया है। यह एक क्रूर बल दृष्टिकोण है, क्योंकि हम सभी संभावित उप-सरणी से गुजर रहे हैं।
ऐसा करने के लिए सरल चरण यहां दिए गए हैं।
चरण 1) max_sum को न्यूनतम पूर्णांक मान से आरंभ करें और चर “begin” और “end” को शून्य से निर्दिष्ट करें।
चरण 2) मान लें कि i और j सरणी के सूचकांक हैं, जहाँ “j” “i” के बराबर से बड़ा है। यह उप-सरणी के आरंभिक सूचकांक को दर्शाता है, और “j” उप-सरणी के अंतिम सूचकांक को दर्शाता है।
चरण 3) “Current_sum” सबअरे का योग रखेगा। वर्तमान योग की गणना करने के बाद, जाँचें कि current_sum, max_sum से अधिक है या नहीं।
चरण 4) यदि current_sum अधिक है, तो max_sum को वर्तमान योग से प्रतिस्थापित करें।
चरण 5) जाँचें कि “j” सरणी के अंत तक पहुँचता है या नहीं। यदि “j” सरणी के अंत तक पहुँचता है, तो “i” बढ़ाएँ और current_sum मान को 0 में बदलें।
चरण 6) इन सभी चरणों का पालन करें, जब तक कि “i” सारणी के अंत तक न पहुंच जाए।
चरण 7) इन दो लूपों के अंत में, max_sum सबसे बड़ा उपसरणी योग रखेगा।
सरल दृष्टिकोण के लिए छद्म कोड
function maximumSubarraySum(): input: array for all possible subArray from array: calculate sum of each sub array 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) दो चर बनाएँ, current_sum, और max_sum.
"Current_sum" एक विशिष्ट सरणी सूचकांक में समाप्त होने वाले अधिकतम योग का मान रखेगा, जबकि "max_sum" अब तक के अधिकतम योग मान को संग्रहीत करेगा।
चरण 2) हम प्रत्येक ऐरे तत्व के लिए current_sum के साथ मान जोड़ेंगे। फिर हम नीचे दी गई दो शर्तों की जाँच करेंगे:
- यदि current_sum वर्तमान तत्व से कम है, तो current_sum मान वर्तमान तत्व होगा।
- यदि max_sum, current_sum से कम है, तो max_sum, current_sum होगा।
चरण 3) संपूर्ण सारणी के लिए पिछले चरण का पालन करते हुए, हमारे पास “max_sum” चर में सबसे बड़ा योग सन्निहित उपसरणी होगी।
कडाने के एल्गोरिथ्म का उदाहरण
हम एक छोटे आकार की सरणी के साथ कडानेस एल्गोरिथ्म का प्रदर्शन करेंगे और सबसे बड़ा योग सन्निहित उपसरणी खोजने के प्रत्येक चरण पर चर्चा करेंगे।
मान लें कि दी गई सारणी निम्नलिखित जैसी है:
कडाने के एल्गोरिथ्म के चरण इस प्रकार हैं:
चरण 1) दो चर बनाएँ, current_sum और max_sum। max_sum को INT_MIN और current_sum को शून्य असाइन करें। (यहाँ, INT_MIN का अर्थ न्यूनतम पूर्णांक संख्या है)।
चरण 2) सूचकांक 0 पर, मान 4 है। अतः current_sum = 0 + 4 या 4. यहाँ current_sum, max_sum से बड़ा है, तो max_sum 4 होगा।
चरण 3) इंडेक्स 1 पर, मान -2 है। इसलिए, current_sum = 4 + (-2) या 2.
इस बार current_sum, max_sum से कम है। परिणामस्वरूप, max_sum का मान अपडेट नहीं किया जाएगा।
चरण 4) अगला मान 1 है। अगर हम इसे current_sum के साथ जोड़ दें, तो current_sum 3 हो जाएगा। फिर भी, max_sum current_sum से ज़्यादा है। इसलिए, max_sum अपडेट नहीं किया जाएगा।
चरण 5) इंडेक्स 3 पर, मान तीन है। हम current_sum को 3 से बढ़ाकर मान को अपडेट करेंगे। इसलिए, current_sum 6 होगा।
इस मामले में, max_sum, current_sum से छोटा है। इसलिए, max_sum को current_sum के मान के साथ अपडेट किया जाएगा।
चरण 6) सरणी के अंतिम तत्व के लिए, हमारे पास -1 है। यदि हम इसे current_sum के साथ जोड़ते हैं, तो current_sum 5 होगा, जो max_sum से छोटा है। इसलिए, max_sum 6 ही रहेगा।
जैसे ही हम सरणी के अंत तक पहुँचते हैं, एल्गोरिथ्म यहाँ समाप्त होता है। अब, “max_sum” में अधिकतम योग उपसरणी शामिल है। जो 5 है। उपसरणी {4,-2,1,3} है।
कडाने के एल्गोरिथ्म के लिए छद्म कोड
function KadaneAlgorithm(): input: array maximum_sum, current_sum = 0 for each elements 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 -10000000 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
सबसे बड़े योग सन्निहित उपसरणी के लिए जटिलता विश्लेषण
सरल दृष्टिकोण दो लूप का उपयोग करता है। यह विधि सबसे बड़ा खोजने के लिए सभी संभावित उप-सरणी योगों की गणना करती है। यह एक क्रूर बल दृष्टिकोण है। प्रत्येक लूप अंत तक चलता है सरणी.
यदि किसी सारणी में कुल N तत्वों, फिर दो लूप का उपयोग करके, हम एन के माध्यम से जाएंगे2 तत्व। नतीजतन, सबसे बड़ा योग सन्निहित उपसरणी खोजने के लिए एक सरल दृष्टिकोण के लिए समय जटिलता होगी O(N2)
. यहाँ, “O” का अर्थ जटिलता फ़ंक्शन है।
दूसरी ओर, कडेन का एल्गोरिथ्म अधिकतम सन्निहित योग उप-सरणी खोजने के लिए डायनामिक प्रोग्रामिंग विधि है। यदि आप उदाहरण या कोड का अनुसरण करते हैं, तो आप देखेंगे कि हम केवल एक लूप का उपयोग कर रहे हैं।
परिणामस्वरूप, यदि इनपुट सरणी का आकार है N, तो कडाने के एल्गोरिथ्म की समय जटिलता O(N) होगी। यह सरल दृष्टिकोण से तेज़ है। उदाहरण के लिए, 100 तत्वों वाली एक सरणी। सरल दृष्टिकोण 100*100 या 10,000 CPU समय लेगा। लेकिन कडाने का एल्गोरिथ्म केवल 100 CPU समय लेगा।