[C++ / Python / Go] 6 lines greedy median sliding window O(N) on sorted array O(NlogN)
The minimum cost of making sorted elements the same is achieved when they are equal to the median. \nThe total cost is equivalent to the sum of the higher half 
The minimum cost of making sorted elements the same is achieved when they are equal to the median. \nThe total cost is equivalent to the sum of the higher half minus the sum of the lower half. \nThis property holds true when the cost is adjusted according to the sliding window.\n\nFor an ascending subarray *nums[i .. j-1]*, let the next median *num = nums[(i+j)>>1]*. \nWhen the window size increments on the right (i.e., *j* increases), *nums[j] - num* is added to the cost. \nConversely, when the window size decrements on the left (i.e., *i* increases), *num - nums[i]* is subtracted from the cost.\n\n\n```c++\nint maxFrequencyScore(vector<int>& nums, long long k) {\n    sort(nums.begin(), nums.end());                     // sort O(NlogN)\n\tint i = 0, j = 0;                                   // initialize window indices\n    while (j < nums.size())                             // sliding window O(N)\n        if ((k += nums[(i + j) >> 1] - nums[j++]) < 0)  // keep expanding optimal window size and increasing the cost\n            k += nums[(i + j) >> 1] - nums[i++];        // move window foward and reduce the cost against overlimit, optimal window size unchanged\n    return j - i;                                       // final maximum optimal window size\n}\n```\n\n```python\ndef maxFrequencyScore(nums, k):\n    nums.sort()\n    i = j = 0\n    while j < len(nums):\n        k -= nums[j] - nums[(i + j) >> 1]\n        j += 1\n        if k < 0:\n            k += nums[(i + j) >> 1] - nums[i]\n            i += 1\n    return j - i\n```\n\n```go\nfunc maxFrequencyScore(nums []int, k int64) int {\n\tsort.Ints(nums)\n\ti, j := 0, 0\n\tfor j < len(nums) {\n\t\tk -= int64(nums[j] - nums[(i+j)>>1])\n\t\tj++\n\t\tif k < 0 {\n\t\t\tk += int64(nums[(i+j)>>1] - nums[i])\n\t\t\ti++\n\t\t}\n\t}\n\treturn j - i\n}\n```
[]