Maximum Value at a Given Index in a Bounded Array LeetCode solution in C++

1
class Solution {
2
 public:
3
  int maxValue(int n, int index, int maxSum) {
4
    int lo = 1, hi = maxSum;
5
    int r = n - index - 1;
6
    int l = index;
7
    long res = 0;
8
    while (lo <= hi) {
9
      int mid = lo + (hi - lo) / 2;
10
      long sum = 0;
11
      long rs = 0, ls = 0, m = mid - 1;
12
      if (r <= m)
13
        rs = m * (m + 1) / 2 - (m - r) * (m - r + 1) / 2; // if we have to calculate 9+8+7+6, sum
14
                                                          // = 9*(9+1)/2 - (9-4)(9-4+1)/2
15
      else
16
        rs = m * (m + 1) / 2 + r - m; // if we encounter the case in which array right to index is
17
                                      // 3,2,1,1,1, sum = 3*(3+1)/2 + 5-2
18
      if (l <= m)
19
        ls = m * (m + 1) / 2 - (m - l) * (m - l + 1) / 2; // similar to above.
20
      else
21
        ls = m * (m + 1) / 2 + l - m;
22

23
      sum = mid + ls + rs;
24

25
      if (sum <= maxSum)
26
        res = mid, lo = mid + 1;
27
      else
28
        hi = mid - 1;
29
    }
30
    return res;
31
  }
32
};