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

किसी नमूने की शुरुआत और अंत स्थिति के आधार पर उप-सरणी कैसे बदलती है, इसका विज़ुअलाइज़ेशन। प्रत्येक संभावित सन्निहित उप-सरणी को रंगीन रेखा पर एक बिंदु द्वारा दर्शाया जाता है। उस बिंदु का 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) डिवाइड-एंड-कॉनकर एल्गोरिदम तैयार किया। इसके तुरंत बाद, शेमोस ने कार्नेगी मेलन विश्वविद्यालय के सेमिनार में एक आयामी समस्या और उसके इतिहास का वर्णन किया, जिसमें जे कडाने भी शामिल हुए, जिन्होंने एक मिनट के भीतर एक O(n)-समय एल्गोरिदम तैयार किया, जो जितना संभव हो उतना फास्ट है। 982 में, डेविड ग्रिज़ ने डिज्क्स्ट्रा की "मानक रणनीति" को लागू करके वही O(n)-समय एल्गोरिथ्म प्राप्त किया; 1989 में, रिचर्ड बर्ड ने बर्ड-मीर्टेंस औपचारिकता का उपयोग करके जानवर-बल एल्गोरिदम के विशुद्ध रूप से बीजीय हेरफेर द्वारा इसे प्राप्त किया।

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

अनुप्रयोग

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

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

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

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

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

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 में बनाए रखा गया है, और एल्गोरिदम की cf. पंक्ति 7 में अब तक देखे गए current_sum के सभी मूल्यों में से अधिकतम के रूप में आसानी से प्राप्त किया जाता है।

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

इस प्रकार, समस्या को निम्नलिखित कोड से हल किया जा सकता है, जिसे नीचे पायथन में व्यक्त किया गया है। यदि इनपुट में कोई धनात्मक तत्व नहीं है (इनपुट रिक्त होने पर भी) तो एल्गोरिदम का यह संस्करण 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 को इसके बजाय ऋणत्मक अनन्तता से आरंभ किया जाना चाहिए

best_sum = - infinity;

और साथ ही लूप के लिए current_sum को max(x, current_sum + x) के रूप में अद्यतन किया जाना चाहिए।

current_sum = max(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