পাইথনে সাজানো অ্যারে তৈরি করতে সর্বাধিক খণ্ডগুলি খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারের সংখ্যা আছে, আমাদের অ্যারেটিকে কিছু সংখ্যক পার্টিশনে ভাগ করতে হবে এবং প্রতিটি আলাদাভাবে সাজাতে হবে। এখন তাদের একত্রিত করার পরে আমরা একটি সাজানো অ্যারে পাব। আমাদের খুঁজে বের করতে হবে সর্বোচ্চ কতগুলো পার্টিশন আমরা তৈরি করতে পারতাম?

সুতরাং, যদি ইনপুটটি [3,2,4,5,5] এর মত হয়, তাহলে আউটপুট হবে 4, যেমন আমরা [3,2], [4], [5], [5] এর মতো পার্টিশন তৈরি করতে পারি।

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

real:=তালিকার সংখ্যা সাজান
p1 :=0,p2 :=1, c :=0
নিম্নলিখিতটি অসীমভাবে করুন, করুন
- পতাকা:=সত্য
- tmp:=সংখ্যার সাবলিস্ট সাজান[সূচী p1 থেকে p2-1]
- j রেঞ্জ 0 থেকে tmp এর আকারের জন্য, করুন
  - যদি tmp[j] বাস্তব[p1+j] এর মত না হয়, তাহলে
    - পতাকা:=মিথ্যা
    - p2 :=p2 + 1
    - লুপ থেকে বেরিয়ে আসুন
  - যদি পতাকা সত্য হয়, তাহলে
    - p1 :=p2
    - p2:=p2+1
    - c :=c + 1
  - যদি p1 সংখ্যার আকার বা p2> সংখ্যার আকারের সমান হয়, তাহলে
    - ফেরত c

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

def solve(nums):
   real=sorted(nums)
   p1,p2,c=0,1,0
   while True:

      flag=True
      tmp=sorted(nums[p1:p2])
      for j in range(len(tmp)):
         if tmp[j]!=real[p1+j]:
            flag=False
            p2+=1
            break

      if flag:
         p1,p2=p2,p2+1
         c+=1
      if p1==len(nums) or p2>len(nums):
         return c

nums = [3,2,4,5,5]
print(solve(nums))

ইনপুট

{3,2,4,5,5}