पुन: डॉलर के उदाहरण पर समस्या "अधिकतम-सबरे"

हाल के लेख "डॉलर के उदाहरण पर" अधिकतम-सबरे "की समस्या को पढ़ने के बाद, 3 बार, मैं थूकना चाहता था। यह आलेख बताता है कि पिछले 5 वर्षों में रूबल के मुकाबले डॉलर की विनिमय दर में अंतर से आप सबसे अधिक कमाई कर सकते हैं। लेखक इस समस्या के लिए अपना "सुंदर" समाधान प्रदान करता है, जिसे उसने खुद पाया (विभाजित और जीतना कहा जाता है, हाँ), और जो O (n lg n) के लिए काम करता है ...

कामरेड, यह शर्मनाक है और ब्लॉग "एल्गोरिथ्म" के लिए अपमानजनक रूप से एक तुच्छ कार्य के लिए स्पष्ट रूप से इष्टतम समाधान प्रकाशित करने के लिए नहीं है। सरणी में सबर्रे तत्वों का अधिकतम योग O (n) में खोजा गया है! यदि केवल विकिपीडिया इस कार्य के लिए श्रद्धेय होगा।

कटौती के तहत सामान्य समाधान।

वास्तव में, कुछ भी "पूर्व-तैयार" करने के लिए कुछ भी नहीं है। लेख में, सब कुछ उल्टा हो गया है। कोटेशन "अधिकतम-सबरे" समस्या को हल करने के लिए पूर्व-तैयार डेटा हैं। लेखक द्वारा हल की गई समस्या "अधिकतम-उपश्रेणी" कार्य को उबाल नहीं पाती है। इसके विपरीत, "अधिकतम-सबरेरी" समस्या का समाधान लेखक ने जो करने की कोशिश की वह नीचे आता है। आपको केवल कुछ सरणी A के लिए i <= j के सूचक हैं, जैसे कि A [j] -A [i] अधिकतम (या न्यूनतम) है।

दो तिथियों को खोजने का कार्य, विनिमय दर मूल्यों में अंतर जिसके लिए अधिकतम है, एक स्थानीय अधिकतम ए [जे] खोजने के लिए कम हो जाता है जैसे कि इसके और न्यूनतम न्यूनतम ए [i] के बीच का अंतर इसे अंतराल (0, जे) पर अधिकतम है । यह गतिशील प्रोग्रामिंग का एक विशिष्ट उदाहरण है, कार्यान्वयन भी अधिक समझ में आता है और लेखक द्वारा दिए गए समाधान की तुलना में बहुत कम दिखता है:

def find(A): currentMin = 1e308 currentMinIndex = None maxDiff = -1e308 bestResult = None for i, v in enumerate(A): if v < currentMin: currentMin, currentMinIndex = v, i if v - currentMin > maxDiff: maxDiff, bestResult = v - currentMin, (currentMinIndex, i) return bestResult, maxDiff 

यहां करेनमेक्टिन, करंटमाइंडेक्स वर्तमान न्यूनतम बोली मान है और अंतराल (0, i) पर इसका सूचकांक है। I-th कदम पर, वर्तमान सर्वोत्तम परिणाम की तुलना वर्तमान पाठ्यक्रम मूल्य और न्यूनतम पाठ्यक्रम के बीच अंतर से की जाती है (वर्तमान में)। यदि वर्तमान अंतर अधिक है - यह सबसे अच्छा के रूप में दर्ज किया गया है, और इसी तरह अंत तक। गणित की भाषा:

 मैक्सिडिफ (0) = -इनफिनिटी
 maxDiff (i) = मैक्स (maxDiff (i-1), A [i] - मिनट (A [0: i])), 
           जहाँ मिनट (A [0: i]) 0 से i के अंतराल में न्यूनतम मान है।

संदर्भ:
पिछला विषय
अधिकतम सबअरे समस्या
गतिशील प्रोग्रामिंग

पुनश्च। मैं एक अलग लेख में जवाब प्रकाशित नहीं करता अगर पिछले विषय मुख्य एक पर नहीं गया। मुझे माफ़ कर देना