पायथन में बाउंडेड ऐरे में दिए गए इंडेक्स पर अधिकतम मान खोजने का प्रोग्राम

मान लीजिए हमारे पास तीन मान n, index और maxSum हैं। एक ऐरे nums पर विचार करें हमें nums[index] ढूंढना है और nums निम्नलिखित शर्तों को पूरा करता है:

• nums का आकार n है।
• n में सभी तत्व पॉजिटिव हैं।
• सभी i के लिए |nums[i] - nums[i+1]| <= 1, जहां 0 <= i < n-1।
• nums के सभी तत्वों का योग maxSum से अधिक नहीं है।
• nums[index] अधिकतम है।

उदाहरण के लिए, यदि इनपुट n = 6, index = 3, maxSum = 8 है, तो आउटपुट 2 होगा क्योंकि हम [1,2,2,2,1,1] जैसा ऐरे प्राप्त कर सकते हैं, जो सभी शर्तों को पूरा करता है, और यहां nums[3] अधिकतम है।

हल करने के चरण

1. left := maxSum // n, right := maxSum + 1
2. ans := 0
3. 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
4. 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

आउटपुट

2