পাইথনে একটি আবদ্ধ অ্যারেতে একটি প্রদত্ত সূচকে সর্বাধিক মান খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের তিনটি মান আছে, n, index এবং maxSum। nums নামক একটি বিন্যাস বিবেচনা করুন আমাদের nums [index] খুঁজে বের করতে হবে এবং nums নিম্নলিখিত শর্তগুলি পূরণ করে -

• সংখ্যার আকার হল n

• n-এর সমস্ত উপাদান ইতিবাচক।

• |সংখ্যা[i] - সংখ্যা[i+1]| <=1 সবার জন্য i, 0 <=i

• সংখ্যার সমস্ত উপাদানের যোগফল maxSum-এর বেশি হয় না।

• সংখ্যা[সূচী] সর্বাধিক করা হয়েছে।

সুতরাং, যদি ইনপুটটি n =6, সূচক =3, maxSum =8 এর মতো হয়, তাহলে আউটপুট হবে 2 কারণ, আমরা [1,2,2,2,1,1] এর মতো একটি অ্যারে পেতে পারি, যা সকলকে সন্তুষ্ট করে। শর্ত, এবং এখানে সংখ্যা[3] সর্বাধিক করা হয়েছে।

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

• বাম :=maxSum/n এর ভাগফল, ডানে :=maxSum + 1

• উত্তর :=0

• যখন বামে <ডানে, কর

  • মধ্য :=বাম + (ডান-বাম)/2

    এর ভাগফল

  • ind_l :=(মধ্য-1 + সর্বাধিক 1 এবং (মধ্য-সূচক)) * (সূচকের সর্বনিম্ন এবং (মধ্য-1) /2 + | সর্বনিম্ন 0, মধ্য-সূচক-1|

    এর ভাগফল

  • ind_r =(মধ্য + সর্বাধিক 1 এবং (মধ্য-(n-সূচক-1))) * (সর্বনিম্ন (n-সূচক) এবং মধ্য)/2 এর ভাগফল + |সর্বনিম্ন 0 এবং (মিড-(n-সূচক) -1)-1)|

  • যদি ind_l + ind_r <=maxSum, তাহলে

    • উত্তর :=মধ্য

    • বাম:=মধ্য+1

  • অন্যথায়,

    • ডান :=মধ্য

• উত্তর ফেরত দিন

উদাহরণ

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

def solve(n, index, maxSum):
   left, right = maxSum//n, maxSum+1
   ans = 0
   while(left<right):
      mid = left + (right-left)//2
      ind_l = (mid-1+max(1,mid-index))*min(index,mid-1)//2 + abs(min(0,mid-index-1))
      ind_r = (mid+max(1,mid-(n-index-1)))*min(n-index, mid)//2+ abs(min(0,mid-(n-index-1)-1))

      if ind_l + ind_r <=maxSum:
         ans = mid
         left = mid+1
      else:
         right = mid
   return ans

n = 6
index = 3
maxSum = 8
print(solve(n, index, maxSum))

ইনপুট

6, 3, 8

আউটপুট

2