Others/798.Smallest-Rotation-with-Highest-Score/Readme.md
我们考虑某一个数的A[i]和它对应的index i。
我们先考虑A[i]<=i,此时根据规则我们知道A[i]对应的得分已经是1。 我们可以知道，每做一次左移，A[i]对应的index就会减1。所以当左移i-A[i]+1次之后，此时的元素位置变成A[i]-1，根据规则得分变为0. 如果将原始数组左移i+1次，那么元素会跑到数组的最后位置（即N-1），根据规则，得分又变成了1。举个例子，如果A="XXXX2XX"，那么左移0次到n-1次，分别对应的得分就是1110011。
我们设立一个差分数组diff，其中diff[k]表示在左移k次之后A[i]对应的得分变化。于是我们就有
diff[0] += 1;
diff[i-A[i]+1] -= 1;
diff[i+1] += 1;
对于A[i]>i，根据规则，初始状态是得0分。当左移i+1次之后，元素跑到了数组的最后一个，一定小于index（即N-1），故得分开始变成1. 当再左移N-A[i]次后，元素跑到了A[i]的位置，此时得分开始变成0.举个例子，如果A="XX4XXXX"，那么左移0次到n-1次，分别对应的得分就是0001110。我们不难总结出：
diff[0] += 0;
diff[i+1] += 1;
diff[i+1+N-A[i]] -= 1;
有了上面两种情况，我们可以处理每个A[i]，计算它所贡献的diff[k]，其中k=0,1,2...,N-1表示左移的次数。
最后在diff数组里找到最大的diff[k]，其中k就对应着rotate多少次能使所有A[i]的得分总和最大。
另外，两种情况也可以统一写成
diff[0]+=1;
diff[(i-A[i]+1+N)%N] -= 1;
diff[i+1] += 1;
PS：这里取模是没有道理也没有意义的。既然已知移动>=N次会重复之前的结果，我们只需要开长度为N+1的diff数组即可（多留一个是为了在某些情况下设置“下降沿”的时候保证diff不越界，本身diff[N]的数值并不会用到）。至于为什么取模之后能AC，是因为题目问的是最大score所对应的rotation index k，随意乱写任何值的diff[0]都不会改变sum的变化趋势，也就不会影响对最优k的判定。