[Java] Intuitive Explanation with easy-to-understand in-line comments
\nclass Solution {\n    /*\n    The question is to find the number of rotations K to maximize the score.\n    We know that only when A[i] <= i can we gain score
```\nclass Solution {\n    /*\n    The question is to find the number of rotations K to maximize the score.\n    We know that only when A[i] <= i can we gain score. The algorithm has 2 steps:\n    1) For each A[i], we get all possible rotations K for wich A[i] <= i as an interval [k1, k2]. \n       If K falls in the interval, that means after K rotations, A[i] will gain 1 point. \n    2) Find K that appears in the most intervals. \n       That means it will gain score for the most elements in A[i]. \n    \n    Details of each step:\n    Step 1: how can we get the interval [k1, k2] ? \n    In general, for each A[i], [(i+1) % N, (i-A[i]+N) % N] will be an interval of K \n    where we will gain points after rotating K times. \n    \n    Step 2: for all the intervals [k1, k2], [k3, k4], ... \n    find the K that appears in the most intervals. We simply loop through all possible K\n    and add one if it enters and interval, and subtract one if it exit from an interval. \n    */\n    public int bestRotation(int[] A) {\n        int N = A.length; \n        int[] rotations = new int[N]; \n        \n        // loop through A[i]\n        for (int i = 0; i < N; i++) {\n            int leftK = (i+1) % N; \n            int rightK = (i-A[i]+1+N) % N; \n            rotations[leftK]++; // gaining interval starts\n            rotations[rightK]--; // losing interval starts; \n            if (leftK > rightK) rotations[0]++; \n        }\n        \n        // loop through number of rotations K \n        // and find the K that overlaps the most intervals \n        int best = -N; \n        int ans = 0, overlaps = 0; \n        for (int k = 0; k < N; k++) {\n            overlaps += rotations[k]; \n            if (overlaps > best) {\n                best = overlaps; \n                ans = k; \n            }\n        }\n        return ans; \n    }\n}\n```
[]