My Solutions
1. Use the sliding window with the help of the presums\n\n/**\n * Time Complexity: O(n * log(n))\n * Space Complexity: O(n)\n * where `n` is the length of the v
**1. Use the sliding window with the help of the presums**\n```\n/**\n * Time Complexity: O(n * log(n))\n * Space Complexity: O(n)\n * where `n` is the length of the vector `nums`\n */\nclass Solution {\n public:\n  int maxFrequencyScore(vector<int> &nums, const long long k) {\n    const int n = static_cast<int>(nums.size());\n    sort(nums.begin(), nums.end());\n    long long presums[n + 1];\n    memset(presums, 0, sizeof(presums));\n    for (int i = 0; i < n; ++i) {\n      presums[i + 1] = presums[i] + nums[i];\n    }\n    \n    int start = 0;\n    for (int end = 0; end < n; ++end) {\n      const int mid = start + ((end - start) >> 1);\n      const long long left = static_cast<long long>(mid - start) * nums[mid] - (presums[mid] - presums[start]);\n      const long long right = (presums[end + 1] - presums[mid + 1]) - static_cast<long long>(end - mid) * nums[mid];\n      if (left + right > k) {\n        ++start;\n      }\n    }\n    return n - start;\n  }\n};\n```\n**2. Use the sliding window**\n```\n/**\n * Time Complexity: O(n * log(n))\n * Space Complexity: O(1)\n * where `n` is the length of the vector `nums`\n */\nclass Solution {\n public:\n  int maxFrequencyScore(vector<int> &nums, const long long k) {\n    const int n = static_cast<int>(nums.size());\n    sort(nums.begin(), nums.end());\n\n    long long cost = 0LL;\n    int start = 0;\n    for (int end = 0; end < n; ++end) {\n      cost += nums[end] - nums[start + ((end - start) >> 1)];\n      if (cost > k) {\n        cost += nums[start] - nums[start + ((end - start + 1) >> 1)];\n        ++start;\n      }\n    }\n    return n - start;\n  }\n};\n```
[]