Binary search + Prefix sum
Intuition\n1. Binary search is usable: \nIf we can get score k, we definately can get k-1. The reachable scores are consective.\n2. Use Prefix sum array\n\n\n# 
# Intuition\n1. Binary search is usable: \nIf we can get score k, we definately can get k-1. The reachable scores are consective.\n2. Use Prefix sum array\n\n\n# Approach\nCalculate the prefix sum array s: s[i]=s[i-1]+a[i-1] (i>0), s[0]=0\nFor a candidate score = right-left+1, check whether times required to make a[left], a[left+1], ..., a[right] all equal to a[(left+right)/2] is larger than k.\n\nformular:\n$~~~~$times = s[right+1] + s[left] - 2*s[i+1] + (tot%2) * a[i];\n&nbsp;where i = (right+left)/2, tot = (right-left)+1\n# Complexity\n- Time complexity:\nO(n*log(m))\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int n;\n    vector<long long> s;\n    bool work(int tot, vector<long long>& s,  vector<int>& a, long long k) {\n        bool flag=false;\n        for (int i=0;i<n;i++) {\n            int left = i-(tot-1)/2;\n            int right = i+tot/2;\n            if (left<0 || right>=n)\n                continue;\n            long long c = s[right+1] + s[left] - 2*s[i+1] + (tot%2) * a[i];\n            if (c<=k){\n                flag=true;\n                break;\n            }\n        }\n        return flag;\n    }\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        n=nums.size();\n        sort(nums.begin(), nums.end());\n        s.push_back(0);\n        for (int i=0;i<n;i++)\n            s.push_back(s[i] + (long long)(nums[i]));\n            \n        int l=0, r=n+1;\n        while (l+1<r) {\n            int mid = (l+r)/2;\n            if (work(mid, s, nums, k))\n                l = mid;\n            else\n                r = mid;\n        }\n        return l;\n    }\n};\n```
['Binary Search', 'Prefix Sum', 'C++']