在Python中找到有界数组中给定索引处的最大值的程序

假设我们有三个值n、index和maxSum。考虑一个名为nums的数组，我们需要找到nums[index]，并且nums满足以下条件：-

nums的大小为n
n中的所有元素都是正数。
对于所有i，0≤i
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 + 1和(mid-index)的最大值的最大值) * ((index和(mid-1)的最小值的商)/2 + |最小值0和mid-index-1|
- ind_r = (mid + 1和(mid-(n-index-1))的最大值的最大值) * ((n-index和mid的最小值的商)/2 + |最小值0和(mid-(n-index-1)-1)|
- 如果ind_l + ind_r <= maxSum，则
  - ans := mid
  - left := mid+1
- 否则，右侧：= 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))