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

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

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

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

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

उदाहरण

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

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]