C++ solution
The value to which all the subarray elements will be set to has to be in the middle such that the number of elements in the lower half and the upper half is exa
The value to which all the subarray elements will be set to has to be in the middle such that the number of elements in the lower half and the upper half is exactly the same\n```\nclass Solution {\npublic:\n  bool canDo(int freq, long long k, vector<int>& nums, vector<long long>& cumSums) {\n    int n = nums.size();\n    for (int i = 0; i <= n - freq; ++i) {\n      int rangeBegin = i;\n      int rangeEnd = i + freq;\n      int mid = (rangeBegin + rangeEnd) / 2;\n      long long rangeBeginHalf = cumSums[mid] - cumSums[rangeBegin];\n      long long secondHalf = cumSums[rangeEnd] -\n        ((freq % 2 == 0) ? cumSums[mid] : cumSums[mid + 1]);\n      long long diff = secondHalf - rangeBeginHalf;\n      if (diff <= k) return true;\n    }\n    return false;\n  }\n  \n  int maxFrequencyScore(vector<int>& nums, long long k) {\n    int n = nums.size();\n    sort(nums.begin(), nums.end());\n    long long cumSum = 0;\n    vector<long long> cumSums;\n    for (int num : nums) {\n      cumSums.push_back(cumSum);\n      cumSum += num;\n    }\n    cumSums.push_back(cumSum);\n    int end = n + 1, begin = 1;\n    while (begin < end) {\n      int mid = (begin + end) / 2;\n      if (canDo(mid, k, nums, cumSums)) {\n        if (end == begin + 1) {\n          return mid;\n        }\n        begin = mid;\n      } else {\n        end = mid;\n      }\n    }\n    return -1;\n  }\n};\n```
[]