Maximize One Value Under a Neighbor-Difference Budget

### Problem Choose a length-n array of positive integers whose neighboring values differ by at most one in absolute value and whose total is at most `maxSum`. Maximize the value at zero-based `index` and return that value, without returning the constructed array. ```cpp class Solution { public: int maxValue(int n, int index, int maxSum); }; ``` ### Examples **Example 1:** ```text n = 3, index = 1, maxSum = 7 Output: 3 Explanation: [2,3,2] uses sum 7; a center value of 4 would require at least 10. ``` **Example 2:** ```text n = 4, index = 0, maxSum = 10 Output: 4 Explanation: [4,3,2,1] fits, while a first value of 5 requires at least 14. ``` ### Constraints - `1 <= n <= maxSum <= 10^9`. - `0 <= index < n`. ### Clarifying Questions The formal source constraint permits index zero, despite introductory wording calling the three integers positive. All chosen array entries must remain at least one. ```hint Inspect the structure What must a candidate array satisfy beyond the value at the selected index? ``` ### Reasoning checkpoints - Show that a claimed peak value admits a complete positive-integer array satisfying every neighbor bound. - Prove that no larger peak fits the total budget, and explain resource use at the maximum bounds. ### Optional extensions How does choosing index at an endpoint change the required sum formula?