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

मान लीजिए कि हमारे पास तीन मान हैं, n, इंडेक्स और मैक्ससम। nums नामक एक सरणी पर विचार करें, हमें nums[index] खोजने होंगे और nums निम्नलिखित शर्तों को पूरा करते हैं -

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

बाएँ :=अधिकतम योग/n का भागफल, दाएँ :=maxSum + 1
उत्तर :=0
जबकि बाएं <दाएं, करें
- मध्य :=बाएँ + भागफल (दाएँ-बाएँ)/2
- ind_l :=(मध्य-1 + अधिकतम 1 और (मध्य-सूचकांक)) * का भागफल (न्यूनतम अनुक्रमणिका और (मध्य-1) /2 + |न्यूनतम 0, मध्य-अनुक्रमणिका-1|
- ind_r =(मध्य + अधिकतम 1 और (मध्य- (एन-इंडेक्स -1))) * भागफल (न्यूनतम (एन-इंडेक्स) और मध्य)/2 + | न्यूनतम 0 और (मध्य- (एन-इंडेक्स) -1)-1)|
- अगर ind_l + ind_r <=मैक्ससम, तो
  - उत्तर:=मध्य
  - बायां :=मध्य+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