---
# System prepended metadata

title: 1802. Maximum Value at a Given Index in a Bounded Array
tags: [Leetcode, Binary Search, Medium]

---

# 1802. Maximum Value at a Given Index in a Bounded Array
###### tags: `Leetcode` `Binary Search` `Medium`
Link: https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/
## 思路
有很多edge case
1. 因为nums里面的值都是positive 不会有0 所以用 $(首项+末项)*项数$ 公式时要考虑末项有没有可能是0 0要填成1 太复杂了 所以最简单的办法是先```maxSum-=n``` 这样nums里面的所有数都变成原来的-1，那么也就不需要考虑把0填成1的情况了
2. 算出来的sum很有可能超过int
## Code
```java=
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        maxSum -= n;
        int start = 0;
        int end = maxSum+1;
        while(start<end){
            int mid = start+(end-start)/2;
            long minArraySum = computeMinSum(n, index, mid);
            if(minArraySum<=maxSum) start = mid+1;
            else{
                end = mid;
            }
        }
        return start;
    }
    private long computeMinSum(int n, int index, int a){
        int b = Math.max(a-index, 0);
        long res = (long)(a+b) * (a-b+1) / 2;
        b = Math.max(a-((n-1)-index), 0);
        res += (long)(a+b) * (a-b+1) / 2;
        return (res-a);
    }
}
```