Derive the (current) fastest implementation
Refer to inline comments for the derivation work\n\n# Intuition\n\nGo through the given examples\n\nSum up the score for all k\n\n# Approach\n\nThe test cases e
Refer to inline comments for the derivation work\n\n# Intuition\n\nGo through the given examples\n\nSum up the score for all k\n\n# Approach\n\nThe test cases expect you to use "prefix sum" for $$O(n)$$ time complexity\n\n1. Initialize the variable `vScore_ge`\n2. Consume each element of `nums` to update `vScore_ge`\n3. Consume each element of `vScore_ge` for the k with highest score\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```cpp []\nclass Solution\n{\npublic:\n    int bestRotation(vector<int>& nums);\n};\n\nint Solution::bestRotation(vector<int>& nums)\n{\n    // [2,3,1,4,0]\n\n    // `vScore_ge[i]` represents partial score for k >= i\n    //\n    // It means that `std::accumulate(vScore_ge.begin(), vScore_ge.begin() + k)` is the score of `k` rotations\n    std::vector<int> vScore_ge(nums.size() + 1u, 0); // +1 to avoid unnecessary branch instruction in adjusting scores\n\n    for (int i = 0, n = (int)nums.size(); i < n; ++i)\n    {\n        int const num = nums[i];\n\n        // e.g. value 2 at position 0\n        //   [2,3,1,4,0]\n        // k      3 2 1\n        //     +1+1+1+1 (k >= i + 1)\n        //     -1       (k >= i + 1 - num + n)\n        //       +1+1+1 (effective change of `vScore_ge`)\n\n        // e.g. value 1 at position 2\n        //   [2,3,1,4,0]\n        // k    1 0 4 3\n        //   -1    -1-1 (k >= i + 1 - num)\n        //         +1+1 (k >= i + 1)\n        //   -1         (effective change of `vScore_ge`)\n\n//        ++vScore_ge[i + 1];\n//        --vScore_ge[i + 1 - num + (num > i ? n : 0)];\n\n        --vScore_ge[(num > i ? 1 + n : 1) - (num - i)];\n    }\n\n    int nScore_i  = vScore_ge[0];\n    int nMaxScore = nScore_i;\n    int nAnswer = 0;\n    for (int i = 1, n = (int)nums.size(); i < n; ++i)\n    {\n        nScore_i += (vScore_ge[i] + 1); // +1 for `++vScore_ge[i + 1]` in the previous for-loop\n\n        nAnswer   = (nMaxScore < nScore_i) ?        i : nAnswer;\n        nMaxScore = (nMaxScore < nScore_i) ? nScore_i : nMaxScore;\n    }\n    return nAnswer;\n}\n\n#include <iostream>\nstatic auto _______ = []() {\n    // turn off sync\n    std::ios::sync_with_stdio(false);\n    // untie in/out streams\n    std::cin.tie(nullptr);\n    return 0;\n}();\n\n```
['Counting', 'Prefix Sum', 'C++']