পাইথনে বাউন্ডেড অ্যারেতে নির্দিষ্ট ইন্ডেক্সে সর্বাধিক মান খুঁজে বের করার প্রোগ্রাম

আমাদের তিনটি মান আছে n, index এবং maxSum। একটি অ্যারে nums বিবেচনা করুন, আমাদের nums[index] বের করতে হবে এবং nums নিচের শর্তগুলো পূরণ করতে হবে:

nums-এর আকার n
nums-এর সব উপাদান ধনাত্মক
সব i (0 ≤ i < n-1) এর জন্য |nums[i] - nums[i+1]| ≤ 1
nums-এর সব উপাদানের যোগফল maxSum-এর চেয়ে বড় হবে না
nums[index] সর্বাধিক হবে

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

সমাধানের ধাপসমূহ

left := maxSum // n, right := maxSum + 1
ans := 0
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))
- যদি ind_l + ind_r <= maxSum হয়, তবে:
  - ans := mid
  - left := mid + 1
- অন্যথায়:
  - right := mid
ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

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