1802. Maximum Value at a Given Index in a Bounded Array
Tags:
Medium
Skills:
Binary SearchGreedy
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu yêu cầu tìm giá trị lớn nhất của index trong array mình build
Approach
1sum = ((end * (end + 1)) / 2) - ((start * (start - 1)) / 2)Time and space complexity:
Solution - Greedy & Binary search
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}