পাইথনে বিন্যাস সাজানোর জন্য অপসারণ করা হবে এমন সংক্ষিপ্ততম সাবারে খুঁজে বের করার প্রোগ্রাম

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

সুতরাং, যদি ইনপুটটি arr =[10,20,30,100,40,20,30,50] এর মত হয়, তাহলে আউটপুট হবে 3 কারণ আমরা [100, 40, 20] মুছে ফেলতে পারি যা 3 দৈর্ঘ্যের সবচেয়ে ছোট সাবয়ারে, এবং এইগুলি অপসারণ করে সবগুলি অ-হ্রাসমান ক্রমে [10,20,30,30,50]৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

• n :=arr এর আকার
• arr :=arr এর বাম দিকে 0 এবং arr এর ডানে ইনফিনিটি ঢোকান
• A,B :=দুটি নতুন খালি তালিকা
• p :=1, q:=arr-2 এর আকার
• M :=0
• যখন p <=q, do
  • যদি arr[p-1] <=arr[p], তাহলে
    • A-এর শেষে arr[p] ঢোকান
    • p :=p + 1
  • অন্যথায় যখন arr[q] <=arr[q+1], তারপর
    • বি-এর শেষে 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]

আউটপুট

3