पायथन में क्रमबद्ध सरणी बनाने के लिए हटाए जाने वाले सबसे छोटे उप-सरणी को खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एआर नामक एक सरणी है, हमें एआर के एक सबरेरे को हटाना होगा जैसे कि एआर में शेष तत्व गैर-घटते क्रम में हैं। हमें निकालने के लिए सबसे छोटी उपसरणी की लंबाई ज्ञात करनी होगी।

इसलिए, यदि इनपुट arr =[10,20,30,100,40,20,30,50] की तरह है, तो आउटपुट 3 होगा क्योंकि हम [100, 40, 20] को हटा सकते हैं जो लंबाई 3 की सबसे छोटी उप-सरणी है, और इन सभी को हटाकर गैर-घटते क्रम में हैं [10,20,30,30,50]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

n :=गिरफ्तारी का आकार
arr :=arr के बाईं ओर 0 और arr के दाईं ओर अनंत डालें
A,B :=दो नई खाली सूचियां
p :=1, q:=arr -2 का आकार
एम:=0
जबकि p <=q, करें
- अगर गिरफ्तारी [p-1] <=गिरफ्तारी [p], तो
  - A के अंत में arr[p] डालें
  - p :=p + 1
- अन्यथा जब एआर [क्यू] <=एआर [क्यू + 1], फिर
  - B के अंत में arr[q] डालें
  - जबकि A खाली नहीं है और A का अंतिम तत्व> B का अंतिम तत्व है
    - A से अंतिम तत्व हटाएं
  - q :=q - 1
- अन्यथा,
  - लूप से बाहर आएं
- M :=अधिकतम M और A का आकार + B का आकार
वापसी एन - एम

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

def solve(arr):
   n = len(arr)
   arr = [0] + arr + [float("inf")]
   A,B=[],[]
   p,q=1,len(arr)-2
   M = 0
   while p <= q:
      if arr[p-1] <= arr[p]:
         A.append(arr[p])
         p += 1
      elif arr[q] <= arr[q+1]:
         B.append(arr[q])
         while A and A[-1] > B[-1]:
            A.pop()
         q -= 1
      else:
         break
      M = max(M, len(A)+len(B))
   return n - M
arr = [10,20,30,100,40,20,30,50]
print(solve(arr))

इनपुट

[10,20,30,100,40,20,30,50]