एक निश्चित लंबाई के खंडों पर अधिकतम खोजने की समस्या

समस्या का बयान

लंबाई N की एक सरणी A को दिया जाता है, और एक नंबर K It N दिया जाता है। इस सरणी के लंबाई K के उप-खंडों में अधिकतम (न्यूनतम, योग ...) खोजना आवश्यक है। यह RMQ समस्या (रेंज न्यूनतम क्वेरी) का एक विशेष मामला है, लेकिन अतिरिक्त प्रतिबंधों के साथ, खोज खंड की निरंतर लंबाई। इस समाधान में, कार्य सरणी के तत्वों को बदलने की संभावना को प्रभावित नहीं करता है। निश्चितता के लिए, हम अधिकतम खोजने पर विचार करेंगे।

फायदे और नुकसान

यह एल्गोरिथ्म O (N) के लिए पूर्व-निर्धारण के साथ, O (1) के लिए निर्धारित लंबाई के उप-खंडों पर अधिकतम खोजने की अनुमति देता है। इस स्थिति में, सहायक मेमोरी के लिए 2 * N की आवश्यकता होती है। लेकिन मुख्य लाभ को एक बहुत ही सरल कार्यान्वयन और समझने योग्य माना जा सकता है। नुकसान यह है कि एल्गोरिथ्म मूल सरणी के तत्वों को बदलने के लिए अनुकूलित नहीं है। यानी एक परिवर्तन संभव है, लेकिन इसके लिए ओ (के) कार्यों के क्रम को पूरा करना आवश्यक होगा।

निर्णय

preprocessing

मूल सरणी A को लंबाई K-1 (क्यों K-1, थोड़ा कम समझें) के खंडों में विभाजित करें। फिर हम दो अतिरिक्त सरणियों B और C की गणना निम्नानुसार करते हैं:

बी में [i] हम वर्तमान ब्लॉक की शुरुआत से ith तत्व तक अंतराल में अधिकतम स्टोर करेंगे;
सी में [i] हम इथ तत्व से अंतराल में अधिकतम को वर्तमान ब्लॉक के अंत तक संग्रहीत करेंगे।

उदाहरण के लिए, बी [2] में हम अधिकतम को ए [0] से ए [२] तक और सी में [२] - ए [२] से ए [३] तक का अधिकतम संग्रह करेंगे। यह स्पष्ट है कि यह ऑपरेशन ओ (एन) में किया जा सकता है। निम्नलिखित आंकड़ा N = 22, K = 5 के लिए एक उदाहरण दिखाता है:

प्रसंस्करण का अनुरोध करें

अब, इस सरल संरचना की मदद से, आप आसानी से लंबाई के सेगमेंट पर अधिकतम पा सकते हैं। हमने विशेष रूप से लंबाई के -1 को ब्लॉक बनाया है ताकि किसी भी क्वेरी के किनारों को हमेशा दो पड़ोसी ब्लॉकों में पड़ें। और, इसलिए, किसी भी अनुरोध के साथ, सीमा में 2 ब्लॉकों की सीमा शामिल होगी। हम इसे टी कहते हैं। सेगमेंट के बाएं किनारे को l, और दाईं ओर r है। अब, अधिकतम प्राप्त करने के लिए, हमें केवल अधिकतम (C [l], B [r]) लेने की आवश्यकता है। दरअसल, L से T तक के अंतराल में C [l] अधिकतम है, और B [r] T से r में अधिकतम है, और इसलिए, C [l] और B [r] में अधिकतम l से अंतराल में अधिकतम होगा। आर।

कार्यान्वयन

सी ++ में सबसे सरल कार्यान्वयन निम्नलिखित है;

vector< int > B, C; void build(const vector< int > A, int k) { int n = A.size(); B.resize(n); C.resize(n); k--; //  B for(int i = 0; i < n; i++) { if(i % k) B[i] = max(A[i], B[i - 1]); else B[i] = A[i]; } //  C C.back() = A.back(); for(int i = n - 2; i >= 0; i--) { if((i + 1) % k) C[i] = max(A[i], C[i + 1]); else C[i] = A[i]; } } int GetMax(int l, int k) { return max(C[l], B[l + k - 1]); } 

उचित संचालन के लिए, यह भी आवश्यक है कि बिल्ड और गेटमैक्स फ़ंक्शन के इनपुट को आपूर्ति की गई K समान हो।

जाहिर है, बिल्ड फ़ंक्शन का यह कार्यान्वयन इष्टतम नहीं है, लेकिन यह सबसे सरल और सीधा है। प्रत्येक अगले चरण में, पिछले एक के आधार पर एक नए मूल्य की गणना की जाती है। नीचे एक तेज़ कार्यान्वयन है।

 void build(const vector< int > A, int k) { int n = A.size(); B.resize(n); C.resize(n); B.front() = A.front(); C.back() = A.back(); k--; for(int i1(1), i2(n - 2); i1 < n; i1++, i2--) { B[i1] = (i1 % k) ? max(A[i1], B[i1 - 1]) : A[i1]; C[i2] = ((i2 + 1) % k) ? max(A[i2], C[i2 + 1]) : A[i2]; } } 

परिणाम

जैसा कि आप देख सकते हैं, एल्गोरिदम कार्यान्वयन के मामले में और समझने के मामले में बहुत सरल है। यह किसी दिए गए लम्बाई के एक उपखंड पर अधिकतम खोजने के लिए O (1) का एक विषम रूप से बेहतर अनुमान देता है। यह संरचना न्यूनतम या राशि खोजने के लिए बदलना आसान है। इसके अलावा, संभावित विकल्पों की अधिकतम संख्या एनके के बराबर होगी, जिसका अर्थ है कि इस संरचना की मदद से सभी संभावित संयोजनों की गणना ओ (एन) के रूप में की जा सकती है। समय के प्रत्येक क्षण में, लंबाई K के केवल दो आसन्न ब्लॉकों को मेमोरी में संग्रहित किया जाना चाहिए, जो अधिक उन्नत कार्यान्वयन में मेमोरी के आकार को कम करेगा।

एल्गोरिथ्म का लेखक वान हर्क का है।

संदर्भ

आरएमक्यू चैलेंज - 1. स्टेटिक आरएमक्यू
RMQ समस्या - 2. लाइन ट्री
स्टैक के संशोधन के माध्यम से एक ही समस्या का समाधान (ई-मैक्सएक्स)
RMQ (ई-मैक्सएक्स) के बारे में थोड़ा और अधिक
बड़ी मात्रा में जानकारी (अंग्रेजी में)