अधिकतम उप-सरणी समस्या अधिकतम स्लाइस समस्या के समान है। यह ट्यूटोरियल C++ में कोडिंग की समस्या पर चर्चा करता है। प्रश्न यह है: किसी सरणी के भीतर क्रमागत संख्याओं के किसी भी संभावित अनुक्रम का अधिकतम योग क्या है? इसका मतलब पूरी सरणी हो सकता है। यह समस्या और किसी भी भाषा में इसका समाधान, अधिकतम उप-सारणी समस्या के रूप में जाना जाता है। सरणी में संभावित नकारात्मक संख्याएं हो सकती हैं।
समाधान कुशल होना चाहिए। इसमें सबसे तेज समय जटिलता होनी चाहिए। अब तक, समाधान के लिए सबसे तेज़ एल्गोरिथम वैज्ञानिक समुदाय में कडाने के एल्गोरिथम के रूप में जाना जाता है। यह लेख C++ के साथ कडाने के एल्गोरिथम की व्याख्या करता है।
डेटा उदाहरण
निम्नलिखित वेक्टर (सरणी) पर विचार करें:
वेक्टर < पूर्णांक > ए = { 5 , - 7 , 3 , 5 , - दो , 4 , - 1 } ;
अधिकतम योग के साथ टुकड़ा (उप-सरणी) अनुक्रम है, {3, 5, -2, 4}, जो 10 का योग देता है। कोई अन्य संभावित अनुक्रम, यहां तक कि संपूर्ण सरणी, तक का योग नहीं देगा 10 का मान। पूरा सरणी 7 का योग देता है, जो कि अधिकतम योग नहीं है।
निम्नलिखित वेक्टर पर विचार करें:
वेक्टर < पूर्णांक > बी = { - दो , 1 , - 3 , 4 , - 1 , दो , 1 , - 5 , 4 } ;
अधिकतम योग के साथ टुकड़ा (उप-सरणी) अनुक्रम है, {4, −1, 2, 1} जो 6 का योग देता है। ध्यान दें कि अधिकतम योग के लिए उप-सरणी के भीतर ऋणात्मक संख्याएं हो सकती हैं।
निम्नलिखित वेक्टर पर विचार करें:
वेक्टर < पूर्णांक > सी = { 3 , दो , - 6 , 4 , 0 } ;
अधिकतम योग वाला टुकड़ा (उप-सरणी) अनुक्रम है, {3, 2} जो 5 का योग देता है।
निम्नलिखित वेक्टर पर विचार करें:
वेक्टर < पूर्णांक > डी = { 3 , दो , 6 , - 1 , 4 , 5 , - 1 , दो } ;
अधिकतम योग के साथ उप-सरणी अनुक्रम है, {3, 2, 6, -1, 4, 5, -1, 2} जो 20 का योग देता है। यह संपूर्ण सरणी है।
निम्नलिखित वेक्टर पर विचार करें:
वेक्टर < पूर्णांक > ई = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , पंद्रह , 4 , - 8 , - पंद्रह , - 22 } ;
यहां अधिकतम रकम के साथ दो उप-सरणी हैं। उच्च योग वह है जिसे अधिकतम उप-सरणी समस्या के समाधान (उत्तर) के रूप में माना जाता है। उप-सरणी हैं: {5, 7} 12 के योग के साथ, और {6, 5, 10, -5, 15, 4} 35 के योग के साथ। बेशक, 35 के योग के साथ टुकड़ा है उत्तर।
निम्नलिखित वेक्टर पर विचार करें:
वेक्टर < पूर्णांक > एफ = { - 4 , 10 , पंद्रह , 9 , - 5 , - बीस , - 3 , - 12 , - 3 , 4 , 6 , 3 , दो , 8 , 3 , - 5 , - दो } ;
अधिकतम रकम के साथ दो उप-सरणी हैं। उच्च योग वह है जिसे अधिकतम उप-सरणी समस्या के समाधान के रूप में माना जाता है। उप-सरणी हैं: {10, 15, 9} 34 के योग के साथ, और {4, 6, 3, 2, 8, 3} के योग के साथ 26। बेशक, 34 के योग के साथ टुकड़ा है उत्तर क्योंकि समस्या उप-सरणी को उच्चतम योग के साथ देखना है, न कि उच्च योग के साथ उप-सरणी को देखना।
कडाने के एल्गोरिथम का विकास करना
ट्यूटोरियल के इस भाग में दी गई जानकारी कडाने की मूल कृति नहीं है। कडाने के एल्गोरिथम को सिखाने का यह लेखक का अपना तरीका है। उपरोक्त वैक्टर में से एक, इसके कुल योग के साथ, इस तालिका में है:
| जानकारी | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | पंद्रह | 4 | -8 | -पंद्रह | -22 |
| चालू हालत में कुल | 5 | 12 | 8 | -दो | -8 | -दो | 3 | 13 | 8 | 23 | 27 | इक्कीस | 16 | -6 |
| अनुक्रमणिका | 0 | 1 | दो | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ग्यारह | 12 | 13 |
किसी इंडेक्स के लिए रनिंग टोटल इंडेक्स के लिए पिछले सभी मानों का योग है। यहां अधिकतम राशि वाले दो क्रम हैं। वे {5, 7} हैं, जो 12 का योग देता है, और {6, 5, 10, -5, 15, 4}, जो 35 का योग देता है। 35 का योग देने वाला क्रम वांछित है .
ध्यान दें कि चल रहे योग के लिए, दो शिखर हैं जो मान हैं, 12 और 27। ये शिखर दो अनुक्रमों के अंतिम अनुक्रमित के अनुरूप हैं।
इसलिए, कडाने के एल्गोरिथ्म का विचार यह है कि दिए गए सरणी में बाएं से दाएं की ओर बढ़ते हुए अधिकतम योगों की तुलना करते हुए रनिंग टोटल किया जाए।
ऊपर से एक और वेक्टर, इसके कुल योग के साथ, इस तालिका में है:
अधिकतम रकम के साथ दो क्रम हैं। वे {10, 15, 9} हैं, जो 34 का योग देता है; और {4, 6, 3, 2, 8, 3} जो 26 का योग देता है। 34 का योग देने वाला क्रम वांछित है।
ध्यान दें कि चल रहे योग के लिए, दो चोटियाँ हैं जो मान हैं, 30 और 13। ये चोटियाँ दो अनुक्रमों के अंतिम अनुक्रमणिका के अनुरूप हैं।
फिर से, कडाने के एल्गोरिथ्म का विचार है कि दिए गए सरणी में बाएं से दाएं की ओर बढ़ते हुए, अधिकतम रकम की तुलना करते हुए रनिंग टोटल करना।
C++ में कडाने के एल्गोरिथम द्वारा कोड
लेख के इस खंड में दिया गया कोड जरूरी नहीं है कि कडाने ने क्या इस्तेमाल किया। हालाँकि, यह उनके एल्गोरिथ्म द्वारा है। कई अन्य C++ प्रोग्रामों की तरह यह प्रोग्राम इसके साथ शुरू होगा:
#शामिल करें#शामिल करें<वेक्टर>
नेमस्पेस एसटीडी का उपयोग करना;
iostream लाइब्रेरी का समावेश है, जो इनपुट और आउटपुट के लिए जिम्मेदार है। मानक नामस्थान का उपयोग किया जाता है।
कडाने के एल्गोरिथ्म का विचार यह है कि दिए गए सरणी में बाएं से दाएं की ओर बढ़ते हुए अधिकतम योगों की तुलना करते हुए कुल योग होना चाहिए। एल्गोरिथ्म के लिए कार्य है:
int maxSunArray ( वेक्टर < पूर्णांक > और ए ) {इंट एन = ए आकार ( ) ;
इंट मैक्ससम = ए [ 0 ] ;
इंट रनटोटल = ए [ 0 ] ;
के लिये ( पूर्णांक मैं = 1 ; मैं < एन; मैं++ ) {
int tempRunTotal = runTotal + A [ मैं ] ; // A . से छोटा हो सकता है [ मैं ]
यदि ( ए [ मैं ] > tempRunTotal )
रनटोटल = ए [ मैं ] ; // में मामला ए [ मैं ] कुल चलने से बड़ा है
वरना
रनटोटल = tempRunTotal;
यदि ( रनटोटल > अधिकतम राशि ) // सभी अधिकतम राशियों की तुलना करना
मैक्ससम = रनटोटल;
}
वापसी अधिकतम राशि;
}
दिए गए सरणी (वेक्टर) का आकार, N निर्धारित किया जाता है। चर, मैक्ससम संभावित अधिकतम राशियों में से एक है। एक सरणी में कम से कम एक अधिकतम योग होता है। चर, रनटोटल प्रत्येक सूचकांक पर चल रहे कुल का प्रतिनिधित्व करता है। वे दोनों सरणी के पहले मान के साथ प्रारंभ किए गए हैं। इस एल्गोरिथम में, यदि सरणी में अगला मान रनिंग टोटल से अधिक है तो वह अगला मान नया रनिंग टोटल बन जाएगा।
एक मुख्य फॉर-लूप है। वेरिएबल, मैक्ससम और रनटोटल से ए [0] की शुरुआत के कारण स्कैनिंग 1 से शुरू होती है और शून्य नहीं होती है जो दिए गए सरणी का पहला तत्व है।
फॉर-लूप में, पहला स्टेटमेंट सभी पिछले मानों के संचित योग में वर्तमान मान जोड़कर एक अस्थायी रनिंग टोटल निर्धारित करता है।
अगला, एक if/else निर्माण है। यदि वर्तमान मान अकेले अब तक के रनिंग टोटल से अधिक है, तो वह सिंगल वैल्यू रनिंग टोटल बन जाता है। यह विशेष रूप से आसान है यदि दिए गए सरणी में सभी मान नकारात्मक हैं। इस मामले में, केवल उच्चतम ऋणात्मक मान ही अधिकतम मान (उत्तर) बन जाएगा। यदि वर्तमान मूल्य अकेले अस्थायी चलने वाले कुल से अधिक नहीं है, तो चलने वाला कुल पिछले चलने वाला कुल और वर्तमान मूल्य बन जाता है, - यह if/else निर्माण का अन्य हिस्सा है।
फॉर-लूप में अंतिम कोड खंड पिछले अनुक्रम (उप-सरणी) के लिए किसी भी पिछले अधिकतम योग और वर्तमान अनुक्रम के लिए किसी भी वर्तमान अधिकतम योग के बीच चयन करता है। इसलिए उच्च मूल्य को चुना जाता है। एक से अधिक अधिकतम उप-सरणी योग हो सकते हैं। ध्यान दें कि रनिंग टोटल बढ़ेगा और गिरेगा, क्योंकि ऐरे को बाएं से दाएं स्कैन किया जाता है। यह गिर जाता है क्योंकि यह नकारात्मक मूल्यों को पूरा करता है।
अंतिम चुना गया अधिकतम उप-सरणी योग फॉर-लूप के बाद वापस कर दिया जाता है।
कडाने के एल्गोरिथम फ़ंक्शन के लिए उपयुक्त C++ मुख्य फ़ंक्शन के लिए सामग्री है:
वेक्टर < पूर्णांक > ए = { 5 , - 7 , 3 , 5 , - दो , 4 , - 1 } ; // { 3 , 5 , - दो , 4 } - > 10int ret1 = maxSunArray ( ए ) ;
अदालत << रिट1 << एंडल;
वेक्टर < पूर्णांक > बी = { - दो , 1 , - 3 , 4 , - 1 , दो , 1 , - 5 , 4 } ; // { 4 , - 1 , दो , 1 } - > 6
int ret2 = maxSunArray ( बी ) ;
अदालत << ret2 << एंडल;
वेक्टर < पूर्णांक > सी = { 3 , दो , - 6 , 4 , 0 } ; // { 3 , दो } - > 5
int ret3 = maxSunArray ( सी ) ;
अदालत << रिट3 << एंडल;
वेक्टर < पूर्णांक > डी = { 3 , दो , 6 , - 1 , 4 , 5 , - 1 , दो } ; // { 3 , दो , 6 , - 1 , 4 , 5 , - 1 , दो } - > 5
int ret4 = maxSunArray ( डी ) ;
अदालत << नेट 4 << एंडल;
वेक्टर < पूर्णांक > ई = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , पंद्रह , 4 , - 8 , - पंद्रह , - 22 } ; // { 6 , 5 , 10 , - 5 , पंद्रह , 4 } - > 35
int ret5 = maxSunArray ( तथा ) ;
अदालत << रिट5 << एंडल;
वेक्टर < पूर्णांक > एफ = { - 4 , 10 , पंद्रह , 9 , - 5 , - बीस , - 3 , - 12 , - 3 , 4 , 6 , 3 , दो , 8 , 3 , - 5 , - दो } ; // { 10 , पंद्रह , 9 } - > 3. 4
int ret6 = maxSunArray ( एफ ) ;
अदालत << सही 6 << एंडल;
इसके साथ, आउटपुट होगा:
10
6
5
बीस
35
3. 4
यहां प्रत्येक पंक्ति उत्तर, क्रम में किसी दिए गए सरणी से मेल खाती है।
निष्कर्ष
कडाने के एल्गोरिदम के लिए समय जटिलता ओ (एन) है, जहां एन दिए गए सरणी में तत्वों की संख्या है। इस बार जटिलता अधिकतम उप-सरणी समस्या के लिए सबसे तेज़ है। अन्य एल्गोरिदम हैं जो धीमे हैं। कडाने के एल्गोरिथ्म का विचार रनिंग टोटल करना है, जबकि अधिकतम योगों की तुलना करते हुए, दिए गए सरणी में बाएं से दाएं की ओर बढ़ते हुए। यदि वर्तमान मान अकेले अब तक चल रहे कुल से अधिक है, तो वह एकल मान नया चलने वाला कुल बन जाता है। अन्यथा, नया रनिंग टोटल पिछले रनिंग टोटल प्लस करंट एलिमेंट है, जैसा कि प्रत्याशित है, जैसा कि दिए गए एरे को स्कैन किया गया है।
विभिन्न संभावित उप-सरणी के लिए एक से अधिक अधिकतम योग हो सकते हैं। सभी संभावित उप-सरणियों के लिए उच्चतम अधिकतम योग चुना जाता है।
चुने गए अधिकतम योग की सीमा के लिए सीमित सूचकांक क्या हैं? - यह कुछ और समय के लिए चर्चा है!
क्राइसो