Maximum Value at a Given Index in a Bounded Array

Intuition

If a peak value at index is feasible, then any smaller peak is also feasible, which makes the answer monotonic and perfect for binary search. For a fixed peak value, the cheapest valid array decreases by exactly 1 on each step away from index and then flattens out at 1 once it cannot decrease any further. The minimal cost of a slope is therefore an arithmetic series that gets clamped to 1s, and we can compute it directly with a closed form. We binary search the peak value and keep the largest one whose minimal total stays within maxSum.

Algorithm walkthrough

1. 1Define a helper that, given a peak value and how many elements sit on one side, returns the smallest possible sum of that side (values step down from peak - 1 and never go below 1).
2. 2Define the total minimal cost of a peak as the left side plus the right side plus the peak itself.
3. 3Binary search the peak value between 1 and maxSum, using long or big-integer arithmetic to avoid overflow.
4. 4For a candidate value, if its total minimal cost is within maxSum, record it and search higher; otherwise search lower.
5. 5Return the largest feasible peak value found.

Implementation

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def side_sum(peak: int, count: int) -> int:
            if count < peak:
                return (peak - 1 + peak - count) * count // 2
            full = peak * (peak - 1) // 2
            ones = count - (peak - 1)
            return full + ones

        def total(peak: int) -> int:
            return side_sum(peak, index) + side_sum(peak, n - index - 1) + peak

        lo, hi = 1, maxSum
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if total(mid) <= maxSum:
                lo = mid
            else:
                hi = mid - 1
        return lo