বাইনারি অ্যারেতে 1s-এর দীর্ঘতম ক্রমাগত ক্রম পেতে 0-এর সূচকগুলি 1 দিয়ে প্রতিস্থাপিত হবে - পাইথনে সেট-2

ধরুন আমাদের একটি বাইনারি অ্যারে আছে। আমাদের 0 এর অবস্থান খুঁজে বের করতে হবে যা 1 দিয়ে প্রতিস্থাপন করা যেতে পারে 1s-এর ক্রমাগত ক্রমটির সর্বাধিক সংখ্যা পেতে।

সুতরাং, যদি ইনপুটটি [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1] এর মত হয়, তাহলে আউটপুট হবে 10, তাই অ্যারে হবে [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]।

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

• i :=0,

• n :=A

  এর আকার

• count_left :=0, count_right :=0

• max_i :=-1, last_i :=-1

• count_max :=0

• যখন আমি

  • যদি A[i] 1 এর মত হয়, তাহলে

    • count_right :=count_right + 1

  • অন্যথায়,

    • যদি last_i -1 এর মত না হয়, তাহলে

      • যদি count_right + count_left + 1> count_max হয়, তাহলে

        • count_max :=count_left + count_right + 1

        • max_i :=last_i

    • last_i :=i

    • count_left :=count_right

    • count_right :=0

  • i :=i + 1

• যদি last_i -1 এর মত না হয়, তাহলে

  • যদি count_left + count_right + 1> count_max, তারপর

    • count_max :=count_left + count_right + 1

    • max_i :=last_i

• max_i

  ফেরত দিন

উদাহরণ

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

def find_max_one_index(A):
   i = 0
   n = len(A)
   count_left = 0
   count_right = 0
   max_i = -1
   last_i = -1
   count_max = 0
   while i < n:
      if A[i] == 1:
         count_right += 1
      else:
         if last_i != -1:
            if count_right + count_left + 1 > count_max:
               count_max = count_left + count_right + 1
               max_i = last_i
            last_i = i
            count_left = count_right
            count_right = 0
      i += 1
   if last_i != -1:
      if count_left + count_right + 1 > count_max:
         count_max = count_left + count_right + 1
         max_i = last_i
   return max_i
A = [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]
print(find_max_one_index(A))

ইনপুট

[1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]

আউটপুট

10