अधिकतम उपसरणी समस्या

किसी नमूने की शुरुआत और अंत स्थिति के आधार पर उप-सरणी कैसे बदलती है, इसका विज़ुअलाइज़ेशन। प्रत्येक संभावित सन्निहित उप-सरणी को रंगीन रेखा पर एक बिंदु द्वारा दर्शाया जाता है। उस बिंदु का y-निर्देशांक नमूने के योग को दर्शाता है। इसका x-निर्देशांक नमूने के अंत का प्रतिनिधित्व करता है, और उस रंगीन रेखा पर सबसे बायां बिंदु नमूने की शुरुआत का प्रतिनिधित्व करता है। इस मामले में, वह सरणी जिससे नमूने लिए गए हैं [2, 3, -1, -20, 5, 10] है।

कंप्यूटर विज्ञान में, अधिकतम योग उपसरणी समस्या, जिसे अधिकतम खंड योग समस्या के रूप में भी जाना जाता है, संख्याओं के दिए गए एक-आयामी सरणी A[1...n] के भीतर, सबसे बड़े योग के साथ एक सन्निहित उपसरणी खोजने का कार्य है। इसे $O(n)$ समय तथा $O(1)$ स्थान में हल किया जा सकता है।

औपचारिक रूप से, कार्य $1\leq i\leq j\leq n$ के साथ सूचकांक $i$ और $j$ को ढूंढना है, जैसे कि योग

$\sum _{x=i}^{j}A[x]$

यथासंभव बड़ा है. (समस्या के कुछ सूत्रीकरण खाली उपसरणी पर भी विचार करने की अनुमति देते हैं; परंपरा के अनुसार, रिक्त उपसरणी के सभी मानों का योग शून्य है।) इनपुट सरणी ए में प्रत्येक संख्या धनात्मक, ऋणात्मक या शून्य हो सकती है।

उदाहरण के लिए, मानों की सारणी [−2, 1, −3, 4, −1, 2, 1, −5, 4] के लिए, सबसे बड़े योग के साथ सन्निहित उपसरणी [4, −1, 2, 1] है। , योग 6 के साथ

इस समस्या के कुछ गुण हैं:

1. यदि सरणी में सभी ऋणेतर संख्याएँ हैं, तो समस्या साधरण है; एक अधिकतम उपसरणी संपूर्ण सरणी होती है।
2. यदि सरणी में सभी गैर-धनात्मक संख्याएँ शामिल हैं, तो एक समाधान आकार 1 का कोई भी उपसरणी है जिसमें सरणी का अधिकतम मान होता है (या खाली उपसरणी, यदि इसकी अनुमति है)।
3. कई भिन्न उप-सरणियों का अधिकतम योग समान हो सकता है।

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

इतिहास

अधिकतम उपसरणी समस्या को 1977 में डिजीटल छवियों में पैटर्न की अधिकतम संभावना अनुमान के लिए एक सरलीकृत मॉडल के रूप में उल्फ ग्रेनेंडर द्वारा प्रस्तावित किया गया था।

ग्रेनांडर वास्तविक संख्याओं की द्वि-आयामी सरणी में, अधिकतम योग के साथ एक आयताकार उपसरणी ढूंढना चाह रहा था। द्वि-आयामी समस्या के लिए एक क्रूर-बल एल्गोरिदम O(n) में चलता है⁶) समय; क्योंकि यह निषेधात्मक रूप से धीमा था, ग्रेनेंडर ने इसकी संरचना में अंतर्दृष्टि प्राप्त करने के लिए एक-आयामी समस्या का प्रस्ताव रखा। ग्रेनेंडर ने एक एल्गोरिदम निकाला जो O(n) में एक-आयामी समस्या को हल करता है²) समय, O(n) के क्रूर बल संचालन समय में सुधार³). जब माइकल शामोस ने समस्या के बारे में सुना, तो उन्होंने रातों-रात इसके लिए एक O(n log n) फूट डालो और जीतो एल्गोरिथ्म तैयार किया। इसके तुरंत बाद, शेमोस ने कार्नेगी मेलन विश्वविद्यालय के सेमिनार में एक-आयामी समस्या और उसके इतिहास का वर्णन किया, जिसमें चल दर भी शामिल थे, जिन्होंने एक मिनट के भीतर एक ओ(एन)-टाइम एल्गोरिदम तैयार किया था, जो यथासंभव तेज़ है। 1982 में, डेविड ग्रिज़ ने एडस्गर डब्लू. डिज्क्स्ट्रा की मानक रणनीति को लागू करके वही O(n)-टाइम एल्गोरिदम प्राप्त किया; 1989 में, रिचर्ड बर्ड (कंप्यूटर वैज्ञानिक) ने बर्ड-मीर्टेंस औपचारिकता का उपयोग करके जानवर-बल एल्गोरिथ्म के विशुद्ध रूप से बीजगणितीय हेरफेर द्वारा इसे प्राप्त किया।

ग्रेनांडर के द्वि-आयामी सामान्यीकरण को O(n) में हल किया जा सकता है³) समय या तो कडेन के एल्गोरिदम को सबरूटीन के रूप में उपयोग करके, या फूट डालो और जीतो दृष्टिकोण के माध्यम से। मिन-प्लस मैट्रिक्स गुणन पर आधारित थोड़ा तेज़ एल्गोरिदम प्रस्तावित किया गया है Tamaki & Tokuyama (1998) और तक Takaoka (2002). इस बात के कुछ प्रमाण हैं कि कोई बहुत तेज़ एल्गोरिदम मौजूद नहीं है; एक एल्गोरिथ्म जो O(n) में द्वि-आयामी अधिकतम उपसरणी समस्या को हल करता है^3−ε) समय, किसी भी ε>0 के लिए, सबसे छोटे पथ समस्या#सभी-जोड़े सबसे छोटे पथ|सभी-जोड़े सबसे छोटे पथ समस्या के लिए एक समान तेज़ एल्गोरिदम का संकेत देगा।

अनुप्रयोग

अधिकतम उपसरणी समस्याएँ कई क्षेत्रों में उत्पन्न होती हैं, जैसे कि जीनोमिक अनुक्रम विश्लेषण और कंप्यूटर दृष्टि

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

कंप्यूटर विज़न में, किसी छवि में सबसे चमकीले क्षेत्र का पता लगाने के लिए बिटमैप छवियों पर अधिकतम-सबरे एल्गोरिदम का उपयोग किया जाता है।

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

रिक्त उपसरणी स्वीकृत

Example run
Execution of Kadane's algorithm on the above example array. Blue: subarray with largest sum ending at i; green: subarray with largest sum encountered so far; a lower case letter indicates an empty array; variable i is left implicit in Python code.

जोसेफ बोर्न कडाने|कडाने का मूल एल्गोरिदम खाली उपसरणी स्वीकार किए जाने पर समस्या संस्करण को हल करता है। यह दिए गए एरे को स्कैन करता है $A[1\ldots n]$ बाएं से दाएं। में $j$वें चरण में, यह सबसे बड़े योग पर समाप्त होने वाली उपसरणी की गणना करता है $j$; यह राशि परिवर्तनीय रूप में रखी जाती है current_sum. इसके अलावा, यह कहीं भी सबसे बड़े योग के साथ उपसरणी की गणना करता है $A[1\ldots j]$, परिवर्तनीय रूप से बनाए रखा गया best_sum, और सभी मूल्यों में से अधिकतम के रूप में आसानी से प्राप्त किया जा सकता है current_sum अब तक देखा, सी.एफ. एल्गोरिथम की पंक्ति 7.

एक लूप अपरिवर्तनीय के रूप में, में $j$वां चरण, का पुराना मान current_sum सब से अधिक सर्वोच्च रखता है $i\in \{1,\ldots ,j\}$ राशि का $A[i]+\cdots +A[j-1]$. इसलिए, current_sum$+A[j]$ सब से अधिक अधिकतम है $i\in \{1,\ldots ,j\}$ राशि का $A[i]+\cdots +A[j]$. मामले को कवर करने के लिए उत्तरार्द्ध को अधिकतम तक विस्तारित करना $i=j+1$, खाली उपसरणी पर भी विचार करना पर्याप्त है $A[j+1\;\ldots \;j]$. यह पंक्ति 6 ​​में असाइन करके किया जाता है $\max(0,$current_sum$+A[j])$ के नये मान के रूप में current_sum, जो उसके बाद सभी से अधिकतम होता है $i\in \{1,\ldots ,j+1\}$ राशि का $A[i]+\cdots +A[j]$.

इस प्रकार, समस्या को निम्नलिखित कोड से हल किया जा सकता है, नीचे पायथन (प्रोग्रामिंग भाषा) में व्यक्त किया गया है। यदि इनपुट में कोई धनात्मक तत्व नहीं है (इनपुट खाली होने सहित) तो एल्गोरिदम का यह संस्करण 0 लौटाएगा।

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = 0
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

एल्गोरिदम को उस मामले में अनुकूलित किया जा सकता है जो खाली उपसरणी की अनुमति नहीं देता है या अधिकतम उपसरणी के आरंभ और समाप्ति सूचकांकों का ट्रैक रखता है।

यह एल्गोरिदम पिछली स्थिति पर समाप्त होने वाली अधिकतम उपसरणी से प्रत्येक स्थिति पर समाप्त होने वाली अधिकतम उपसरणी की गणना करता है, इसलिए इसे गतिशील प्रोग्रामिंग के एक तुच्छ मामले के रूप में देखा जा सकता है।

कोई खाली उपसरणी स्वीकृत नहीं

समस्या के उस प्रकार के लिए जो खाली उपसरणी की अनुमति नहीं देता, best_sum इसके बजाय ऋणात्मक अनन्तता से प्रारंभ किया जाना चाहिए <सिंटैक्सहाइलाइट लैंग = पायथन लाइन स्टार्ट = 3 >

   सर्वोत्तम_योग = - अनन्तता;

</सिंटैक्सहाइलाइट> और फॉर लूप में भी current_sum के रूप में अद्यतन किया जाना चाहिए max(x, current_sum + x). <सिंटैक्सहाइलाइट लैंग = पायथन लाइन स्टार्ट = 6 >

       current_sum = अधिकतम(x, current_sum + x)

</सिंटैक्सहाइलाइट> उस स्थिति में, यदि इनपुट में कोई धनात्मक तत्व नहीं है, तो लौटाया गया मान सबसे बड़े तत्व का होता है (यानी, 0 के निकटतम मान), या यदि इनपुट खाली था तो नकारात्मक अनंत होता है। शुद्धता के लिए, इनपुट सरणी खाली होने पर एक अपवाद उठाया जाना चाहिए, क्योंकि खाली सरणी में अधिकतम गैर-रिक्त उपसरणी नहीं होती है। यदि सरणी गैर-रिक्त है, तो संख्यात्मक और गैर-संख्यात्मक मानों के मिश्रण से बचने के लिए, यदि आवश्यक हो, तो इसके पहले तत्व का उपयोग नकारात्मक अनंत के स्थान पर किया जा सकता है।

सर्वोत्तम उपसरणी की स्थिति की गणना करना

अधिकतम उपसरणी के आरंभ और समाप्ति सूचकांकों पर भी नज़र रखने के लिए एल्गोरिदम को संशोधित किया जा सकता है।

जिस तरह से यह एल्गोरिदम इष्टतम उप-संरचनाओं का उपयोग करता है (प्रत्येक स्थिति पर समाप्त होने वाली अधिकतम उप-सरणी की गणना संबंधित लेकिन छोटे और ओवरलैपिंग उप-समस्या से सरल तरीके से की जाती है: पिछली स्थिति पर समाप्त होने वाली अधिकतम उप-सरणी) इस एल्गोरिदम को गतिशील प्रोग्रामिंग के एक सरल/तुच्छ उदाहरण के रूप में देखा जा सकता है।

जटिलता

कडेन के एल्गोरिदम की रनटाइम जटिलता है $O(n)$ और इसकी अंतरिक्ष जटिलता है $O(1)$.

सामान्यीकरण

उच्च-आयामी सरणियों के लिए समान समस्याएं उत्पन्न हो सकती हैं, लेकिन उनके समाधान अधिक जटिल हैं; देखें, उदाहरणार्थ, Takaoka (2002). Brodal & Jørgensen (2007) ने दिखाया कि इष्टतम समय सीमा में एक-आयामी सरणी में k सबसे बड़े उपसरणी योगों को कैसे खोजा जाए $O(n+k)$.

अधिकतम योग k-डिसजॉइंट सबरेज़ की गणना इष्टतम समय सीमा में भी की जा सकती है $O(n+k)$ .

यह भी देखें

• सबसेट योग समस्या

संदर्भ

• Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016), "Tight Hardness Results for Maximum Weight Rectangles", Proc. 43rd International Colloquium on Automata, Languages, and Programming: 81:1–81:13, doi:10.4230/LIPIcs.ICALP.2016.81, S2CID 12720136
• Bae, Sung Eun (2007), Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem (PDF) (Ph.D. thesis), University of Canterbury, S2CID 2681670, archived from the original (PDF) on 2017-10-26.
• Bengtsson, Fredrik; Chen, Jingsen (2007), Computing maximum-scoring segments optimally (PDF) (Research report), Luleå University of Technology
• Bentley, Jon (1984), "Programming Pearls: Algorithm Design Techniques", Communications of the ACM, 27 (9): 865–873, doi:10.1145/358234.381162, S2CID 207565329
• Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1
• Bird, Richard S. (1989), "Algebraic Identities for Program Calculation" (PDF), The Computer Journal, 32 (2): 122–126, doi:10.1093/comjnl/32.2.122
• Brodal, Gerth Stølting; Jørgensen, Allan Grønlund (2007), "A linear time algorithm for the k maximal sums problem", Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 4708, Springer-Verlag, pp. 442–453, doi:10.1007/978-3-540-74456-6_40.
• Gries, David (1982), "A Note on the Standard Strategy for Developing Loop Invariants and Loops" (PDF), Science of Computer Programming, 2 (3): 207–241, doi:10.1016/0167-6423(83)90015-1, hdl:1813/6370
• Takaoka, Tadao (2002), "Efficient algorithms for the maximum subarray problem by distance matrix multiplication", Electronic Notes in Theoretical Computer Science, 61: 191–200, doi:10.1016/S1571-0661(04)00313-5.
• Tamaki, Hisao; Tokuyama, Takeshi (1998), "Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication", Proceedings of the 9th Symposium on Discrete Algorithms (SODA): 446–452, retrieved November 17, 2018

बाहरी संबंध

• TAN, Lirong. "Maximum Contiguous Subarray Sum Problems" (PDF). Archived from the original (PDF) on 2015-10-10. Retrieved 2017-10-26.
• Mu, Shin-Cheng (2010). "The Maximum Segment Sum Problem: Its Origin, and a Derivation".
• "Notes on Maximum Subarray Problem". 2012.
• www.algorithmist.com
• alexeigor.wikidot.com
• greatest subsequential sum problem on Rosetta Code
• geeksforgeeks page on Kadane's Algorithm