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

1function maxValue(n: number, index: number, maxSum: number): number {
2    // Hàm tính tổng của một đoạn mảng giảm dần từ giá trị `peak`
3    const calcSum = (count: number, peak: number): number => {
4        if (peak >= count) {
5            // Nếu đỉnh đủ lớn để bao phủ toàn bộ đoạn
6            return (peak * (peak + 1)) / 2 - ((peak - count) * (peak - count + 1)) / 2;
7        } else {
8            // Nếu đỉnh nhỏ hơn số lượng phần tử, thêm các phần tử dư bằng 1
9            return (peak * (peak + 1)) / 2 + (count - peak);
10        }
11    };
12
13    // Tìm kiếm nhị phân
14    let left = 1, right = maxSum;
15
16    while (left < right) {
17        const mid = Math.floor((left + right + 1) / 2);
18
19        // Tính tổng bên trái và bên phải
20        const leftSum = calcSum(index, mid - 1); // Bên trái từ [0, index-1]
21        const rightSum = calcSum(n - index - 1, mid - 1); // Bên phải từ [index+1, n-1]
22
23        // Tổng toàn bộ mảng
24        const total = leftSum + rightSum + mid;
25
26        if (total <= maxSum) {
27            left = mid; // Tăng giới hạn dưới nếu hợp lệ
28        } else {
29            right = mid - 1; // Giảm giới hạn trên nếu không hợp lệ
30        }
31    }
32
33    return left;
34}