পাইথনে অ্যারে সর্টেড করতে সবচেয়ে ছোট সাবঅ্যারে সরিয়ে দিয়ে দৈর্ঘ্য নির্ণয়

একটি অ্যারে arr দেওয়া থাকলে, একটি সাবঅ্যারে সরিয়ে দিয়ে বাকি উপাদানগুলো নন-ডিক্রিজিং অর্ডারে আনার জন্য সবচেয়ে ছোট সাবঅ্যারের দৈর্ঘ্য খুঁজে বের করতে হবে।

উদাহরণ:

ইনপুট: arr = [10,20,30,100,40,20,30,50]

আউটপুট: 3 কারণ [100, 40, 20] (দৈর্ঘ্য ৩) সরিয়ে দিলে বাকি [10,20,30,30,50] নন-ডিক্রিজিং হয়।

সমাধানের পদ্ধতি:

1. n = len(arr)
2. অ্যারের বামে 0 এবং ডানে infinity যোগ করুন: arr = [0] + arr + [float("inf")]
3. দুটি খালি লিস্ট A, B এবং পয়েন্টার p=1, q=len(arr)-2 আরম্ভ করুন
4. M = 0 (সর্বোচ্চ ধরে রেখা উপাদান সংখ্যা)
5. while p <= q লুপ চালান:
• যদি arr[p-1] <= arr[p]: A.append(arr[p]), p += 1
• অন্যথায় যদি arr[q] <= arr[q+1]: B.append(arr[q]), তারপর while A and A[-1] > B[-1]: A.pop(), q -= 1
• অন্যথায় লুপ ব্রেক করুন
• M = max(M, len(A) + len(B))
6. রিটার্ন 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))  # আউটপুট: 3

টেস্ট কেস:

ইনপুট: [10,20,30,100,40,20,30,50]

আউটপুট: 3