Binary search + prefixSum
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nThe basic idea is for a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe basic idea is for a index i , how much we can extend that index so that cost to convet all the element in that subarray to the median of that subarray is less then the value of k , which can be easily done with binary search. \n\n\n# Complexity\n- Time complexity:\n- N*log(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\nprivate:\n    long long rangeSum(int l , int r , vector<long long>& a) {\n        if(l == 0) return a[r];\n        return a[r] - a[l - 1];\n    }\n    \n    bool helper(vector<int>& nums , vector<long long>& pre , int l , int r , map<int , vector<int>>& mp , long long k) {\n        long long ind = (l + r) / 2;\n        long long  ele = nums[ind];\n        long long index = lower_bound(mp[ele].begin() , mp[ele].end() , ind) - mp[ele].begin();\n        index = mp[ele][index];\n        long long sum1 = rangeSum(l , index , pre);\n        long long sum2 = rangeSum(index , r , pre);\n        sum1 = (index - l + 1) * ele - sum1;\n        sum2 = sum2 - (r - index + 1) * ele;\n        \n        sum1 += sum2;\n        \n        return (sum1 <= k);\n    }\npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        int n = nums.size();\n        vector<long long> pre(n);\n        \n        sort(nums.begin() , nums.end());\n        \n        map<int , vector<int>> mp;\n        mp[nums[0]].push_back(0);\n        pre[0] = nums[0];\n        \n        for(int i = 1; i < n; i++) {\n            mp[nums[i]].push_back(i);\n            pre[i] =  pre[i - 1] + nums[i]; \n        }\n        \n        int len = 0;\n        \n        for(int i = 0; i < n; i++) {\n            int low = i , high = n - 1;\n            int ans = -1;\n            while(low <= high) {\n                int mid = (low + high) >> 1;\n                if(helper(nums , pre , i , mid , mp , k)) {\n                    ans = mid - i + 1;\n                    low = mid + 1;\n                }\n                else {\n                    high = mid - 1;\n                }\n            }\n            // cout << i << " " << ans << endl;\n            len = max(len , ans);\n        }\n        return len;\n    }\n\n};\n```
['Binary Search', 'Prefix Sum', 'C++']