एक स्पैर मैट्रिक्स

Question

में अधिकतम योग सबक्टेंगल को NxN मैट्रिक्स में अधिकतम योग उपखंड को ढूँढना O(n^3) समय में 2-डी कडाने के एल्गोरिदम का उपयोग करके किया जा सकता है, जैसा कि अन्य पदों में बताया गया है। हालांकि, यदि मैट्रिक्स स्पैस है, विशेष रूप से O(n) गैर-शून्य प्रविष्टियां, O(n^3) समय पीटा जा सकता है?

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

Answer 1

हां, यह बेहतर किया जा सकता है।

सबसे पहले, के जो O(logn) समय

में करने के लिए

1. अद्यतन अंतर्निहित -1 डी सरणी के किसी एक मूल्य की अनुमति देता है O(1) में सरणी की अधिकतम subarray की राशि का पता लगाएं एक डेटा संरचना के बारे में सोचते हैं समय

असल में, एक संतुलित बाइनरी पेड़ जो नीचे जैसा दिखता है, वह काम कर सकता है। पेड़ की संरचना को इस प्रकार वर्णित किया जा सकता है:

1. पेड़ का प्रत्येक पत्ता नोड सरणी के प्रत्येक तत्व को दर्शाता है।
2. यदि कोई आंतरिक नोड कवर [a, b] है, तो इसके बाएं बच्चे को [a, c] रेंज शामिल है और इसका दायां बाल कवर [c + 1, b] है, जहां c = floor((a + b)/2)) है।

3. रूट नोड कवर [1, n] है।

        O 
           / \ 
          /  \ 
          /   \ 
         /    \ 
         /     \ 
         O      O 
        / \     / \ 
       / \    / \ 
       /  \    /  \ 
       O   O   O   O 
   /\  /\  /\  /\ 
   o  o  o  o  o  o  o  o 
   A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 
   

वहाँ 4 (पत्र-गांठ और आंतरिक नोड्स सहित) प्रत्येक नोड v से जुड़ी क्षेत्रों हैं:

• S[v]: v की श्रेणी में सभी मानों का योग
• M[v] : अधिकतम subarray sum v की रेंज
• L[v]: maximu का योग मीटर subarray कि v के बाईं ओर पर शुरू होता है की रेंज
• R[v]: अधिकतम subarray का योग है कि v के दाईं ओर पर समाप्त होता है की रेंज

उपरोक्त परिभाषाओं के आधार पर हम मिल सकता है निम्नलिखित को अद्यतन करने के नियम:

• किसी भी पत्ता नोड v, S[v] = A[v] के लिए, M[v] = L[v] = R[v] = max{0, A[v]}
• किसी भी आंतरिक नोड v के लिए और अपने बच्चों l और r,
  
  • S[v] = S[l] + S[r]
  • M[v] = max{M[l], M[r], R[l] + L[r]}
  • L[v] = max{L[l], L[r] + S[l]}
  • R[v] = max{R[r], R[l] + S[r]}

अंत में, हम संचालन शुरुआत में उल्लेख किया है लागू कर सकते हैं।

• A[i] अद्यतन करने के लिए, हम पेड़ में इसी पत्ती नोड मिल जाए, और इसके बाद के संस्करण नियमों का उपयोग कर जड़ करने के लिए अपने मार्ग के किनारे के खेतों अद्यतन कर सकते हैं।
• अधिकतम सबएरे योग केवल M[root] है।

अब चर्चा करें कि इस डेटा संरचना का उपयोग करके अधिकतम आयत कैसे प्राप्त करें। यदि हम ऊपरी पंक्ति और आयताकार की निचली पंक्ति को i वें और j वें पंक्तियों में ठीक करते हैं, तो समस्या 1 डी अधिकतम सबएरे योग समस्या हो जाती है, जहां A[k] = sum{B[i..j, k]}। मुख्य अंतर्दृष्टि यह है कि, एक निश्चित i के लिए, यदि हम j आरोही क्रम में गणना करते हैं, तो हम अंतर्निहित 1 डी सरणी को बनाए रखने के लिए उपर्युक्त डेटा संरचना का उपयोग कर सकते हैं और उत्तर को बहुत तेज़ी से ढूंढ सकते हैं।

result = 0 
for i in (1, 2, ..., n) 
    set all fields of the binary tree T to 0 
    for j in (i, i + 1, ..., n) 
     for any k where B[j, k] != 0 
      T.update(k, A[k] + B[j, k]) 
     result = max{M[root], result} 
return result 

मान लीजिए मैट्रिक्स m गैर शून्य तत्व शामिल हैं, इस एल्गोरिथ्म के समय जटिलता O(mn logn) है: स्यूडोकोड विचार वर्णन करता है। आपके मामले में m = O(n), इसलिए समय जटिलता O(n^2 logn) है और O(n^3) से बेहतर है।