 [C++/Java/Python] Solution with Explanation
Key point\nDon\'t calculate the score for K=0, we don\'t need it at all.\n(I see almost all other solutions did)\nThe key point is to find out how score changes
**Key point**\nDon\'t calculate the score for ```K=0```, we don\'t need it at all.\n(I see almost all other solutions did)\nThe key point is to find out how score changes when ```K++```\n\n**Time complexity:**\n\u201CA will have length at most 20000.\u201D\nI think it means you should find a O(N) solution.\n\n**How dosen score change when K++ ?**\n* **Get point**\nEach time when we rotate, we make index ```0``` to index ```N-1```, then we get one more point.\nWe know that for sure, so I don\'t need to record it.\n\n* **Lose point**\n```(i - A[i] + N) % N``` is the value of K making ```A[i]\'s``` index just equal to ```A[i]```.\nFor example, If ```A[6] = 1```, then ```K = (6 - A[6]) % 6 = 5``` making ```A[6]``` to ```index 1``` of new array.\nSo when ```K=5```, we get this point for ```A[6]```\nThen if ```K``` is bigger when ```K = (i - A[i] + 1) % N```, we start to lose this point, making our score -= 1\nAll I have done is record the value of ```K```  for all ```A[i]``` where we will lose points.\n\n* **```A[i]=0```**\nRotation makes no change for it, becasue we alwars have ```0 <= index```.\nHowever, it is covered in "get point" and "lose point".\n\n**Explanation of codes**\n1. Search the index where score decrease and record this changement to a list ```change```.\n2. A simple for loop to calculate the score for every ```K``` value. \n```score[K] = score[K-1] + change[K]```\nIn my codes I accumulated  ```changes``` so I get the changed score for every ```K``` value compared to ```K=0``` \n3. Find the index of best score.\n\n\nC++:\n```\n    int bestRotation(vector<int>& A) {\n        int N = A.size();\n        int change[N] = {0};\n        for (int i = 0; i < N; ++i) change[(i - A[i] + 1 + N) % N] -= 1;\n        for (int i = 1; i < N; ++i) change[i] += change[i - 1] + 1;\n        return distance(change, max_element(change, change + N));\n    }\n```\nJava\n```\n    public int bestRotation(int[] A) {\n        int N = A.length;\n        int change[] = new int[N];\n        for (int i = 0; i < N; ++i) change[(i - A[i] + 1 + N) % N] -= 1;\n        int max_i = 0;\n        for (int i = 1; i < N; ++i) {\n            change[i] += change[i - 1] + 1;\n            max_i = change[i] > change[max_i] ? i : max_i;\n        }\n        return max_i;\n    }\n```\nPython\n```\n    def bestRotation(self, A):\n        N = len(A)\n        change = [1] * N\n        for i in range(N): change[(i - A[i] + 1) % N] -= 1\n        for i in range(1, N): change[i] += change[i - 1]\n        return change.index(max(change))\n
[]