> For the complete documentation index, see [llms.txt](https://zhenchaogan.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhenchaogan.gitbook.io/leetcode-solution/leetcode-1802-maximum-value-at-a-given-index-in-a-bounded-array.md).

# LeetCode 1802. Maximum Value at a Given Index in a Bounded Array

You are given three positive integers `n`, `index` and `maxSum`. You want to construct an array `nums` **(0-indexed)** that satisfies the following conditions:

* `nums.length == n`
* `nums[i]` is a **positive** integer where `0 <= i < n`.
* `abs(nums[i] - nums[i+1]) <= 1` where `0 <= i < n-1`.
* The sum of all the elements of `nums` does not exceed `maxSum`.
* `nums[index]` is **maximized**.

Return `nums[index]` of the constructed array.

Note that `abs(x)` equals `x` if `x >= 0`, and `-x` otherwise.

**Example 1:**

```
Input: n = 4, index = 2,  maxSum = 6
Output: 2
Explanation: The arrays [1,1,2,1] and [1,2,2,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.
```

**Example 2:**

```
Input: n = 6, index = 1,  maxSum = 10
Output: 3
```

**Constraints:**

* `1 <= n <= maxSum <= 10^9`
* `0 <= index < n`

## Solution

[English Version in Youtube](https://youtu.be/YaxcdotEiwY)

[中文版解答Youtube Link](https://youtu.be/zDcsb9GYsC8)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1oz4y117Yb/)

```
class Solution {
    
    long getSumInRange(long peak, int length) {
        long sum = 0;
        if (length > peak) {
            sum += (1 + peak) * peak / 2;
            sum += (length - peak);
        } else {
            long minimum = peak - length + 1;
            sum += (minimum + peak) * length / 2;
        }
        return sum;
    }
    
    bool check(int n, int index, int maxSum, int peak) {
        long sum = getSumInRange(peak, index + 1) + getSumInRange(peak, n - index) - peak;
        return sum > (long)maxSum;
    }
    
public:
    int maxValue(int n, int index, int maxSum) {
        int left = 1;
        int right = maxSum;
        int ans = 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            bool exceed = check(n, index, maxSum, mid);
            if (exceed) {
                right = mid - 1;
            } else {
                ans = mid;
                left = mid + 1;
            }
        }
        
        return ans;
    }
};
```