1
class Solution {
2
 public:
3
  int bestRotation(vector<int> &nums) {
4
    int sz = nums.size();
5
    vector<int> pointsForIShifts(2 * sz + 1, 0);
6
    for (int i = 0; i < sz; i++) {
7
      int l = 0, h = 0;
8
      if (nums[i] <= i) {
9
        l = 0;
10
        h = i - nums[i];
11
        pointsForIShifts[l] += 1;
12
        pointsForIShifts[h + 1] -= 1;
13
      }
14
      l = i + 1;
15
      h = i + sz - nums[i];
16
      pointsForIShifts[l] += 1;
17
      pointsForIShifts[h + 1] -= 1;
18
    }
19
    int maxP = pointsForIShifts[0], k = 0;
20
    for (int i = 1; i < pointsForIShifts.size(); i++) {
21
      pointsForIShifts[i] += pointsForIShifts[i - 1];
22
      if (pointsForIShifts[i] > maxP) {
23
        maxP = pointsForIShifts[i];
24
        k = i;
25
      }
26
    }
27
    return k;
28
  }
29
};