Native C++ implementation - 47ms; time complexity = O(NlogN) , space = O(N)
Simple implementation;\n\nFirstly calculate the score of input; \nMake a priority queue in acsending order; \nPut all non-negtive dfff of i - A[i] into priority
Simple implementation;\n\nFirstly calculate the score of input; \nMake a **priority queue** in acsending order; \nPut all non-negtive dfff of i - A[i] into priority queue.\n\nThen do **1 pass** traverse **by a loop variable = shift, shift is from 1 to A.size() -1**;\nEvery time we do shift, since it is a left shift, **A[shift-1] become the tail of A; it is, A[shift-1] becomes A[A.size()-1].**\n**Also, all the diff values diff[i] beomes diff[i] -1 by the decrease of map index (caused by left-shift).**\nSince we only care about the non-negtive valuse (all negtive values will never become non-negtive by subtract one),\na priority queue to remeber the non-negtive values is enough.\nThen score will be changed by 2 cases:\n**case 1. when A[shift-1] <= A.size() -1 : score++;\ncase 2: when shift > q.front(); it means the shift makes some diff values become negtive (originally it is non-negtive). for each of them, score--;**\nRemember to push case 1\'s diff into q also since it may become negtive after some shifts.\n\n**Time complexity: O(NlogN): one pass scan & insertion of new diff if it needs. \nSpace complexiy: O(N) - depend on priority queue.**\n\n```\nclass Solution {\npublic:\n    int bestRotation(vector<int>& A) {\n\t\tint gain = 0;\n\t\tint r;\n\t\tpriority_queue<int, vector<int>, greater<int>> q;\n\t\tfor (int i = 0; i < A.size(); i++) {\n\t\t\tint diff = i - A[i];\n\t\t\tif (diff >= 0) {\n\t\t\t\tgain++;\n\t\t\t\tq.push(diff);\n\t\t\t}\n\t\t}\n\t\tint current = gain;\n\t\tr = 0;\n\t\tfor (int shift = 1; shift <= A.size() - 1; shift++) {\n\t\t\twhile (!q.empty() && (shift > q.top())) {\n\t\t\t\tq.pop();\n\t\t\t\tcurrent--;\n\t\t\t}\n\t\t\tif (A[shift - 1] <= (A.size() - 1)) {\n\t\t\t\tcurrent++;\n\t\t\t\tq.push(shift + (A.size() - 1) - A[shift - 1]);\n\t\t\t}\n\t\t\tif (current > gain) {\n\t\t\t\tr = shift;\n\t\t\t\tgain = current;\n\t\t\t}\n\t\t}\n\t\treturn r;\n    }\n};\n```
[]