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: nums = [1,2,2,1] is one array that satisfies all the conditions.
There are no arrays that satisfy all the conditions and have nums == 3, so 2 is the maximum nums.
```

Example 2:

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

Constraints:

• `1 <= n <= maxSum <= 109`
• `0 <= index < n`

1802. Maximum Value at a Given Index in a Bounded Array
``````struct Solution;

impl Solution {
fn max_value(n: i32, index: i32, max_sum: i32) -> i32 {
let mut l = 1i64;
let mut r = max_sum as i64;
let n = n as usize;
let index = index as usize;
let mut res = 0;
let kl = index as i64;
let kr = (n - index - 1) as i64;
while l <= r {
let m = (l + (r - l) / 2) as i64;
let sum = helper(m, kl) + m + helper(m, kr);
if sum > max_sum as i64 {
r = m - 1;
} else {
res = res.max(m);
l = m + 1;
}
}
res as i32
}
}

fn helper(m: i64, k: i64) -> i64 {
if m > k {
(m - 1 + m - 1 - k + 1) * k / 2
} else {
(m - 1 + 1) * (m - 1) / 2 + (k - m + 1)
}
}

#[test]
fn test() {
let n = 4;
let index = 2;
let max_sum = 6;
let res = 2;
assert_eq!(Solution::max_value(n, index, max_sum), res);
let n = 6;
let index = 1;
let max_sum = 10;
let res = 3;
assert_eq!(Solution::max_value(n, index, max_sum), res);
}
``````