[Python3] Prefix Sum + Sliding Window
Intuition\nIt is useful to notice that the maximum frequency of an element after applying the operations will always be a specific num in nums. Thus, if we sort
# Intuition\nIt is useful to notice that the maximum frequency of an element after applying the operations will always be a specific `num` in `nums`. Thus, if we sort the array, then we only need to analyze contiguous subarrays to minimize calculations.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nFirst sort the array, then use sliding window to find the minimum operations needed such that all elements of the subarray become the same (which is the `median` of the subarray). If the minimum operations needed  is less than or equal to `k`, then it means that the current subarray is valid and we continue moving the `right` pointer. Otherwise, we shrink the `left` pointer until we obtain a valid subarray.\n\nThe minimum operations needed such that all elements of a given subarray become the same can be obtained in `O(1)` by using a `prefix sum`.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n\\log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n        nums.sort()\n        pfsum = [0]\n        for i in range(n):\n            pfsum.append(pfsum[-1] + nums[i])\n            \n        def check(left, right):\n            mid = left + (right - left + 1) // 2\n            part1 = nums[mid] * (mid - left) - (pfsum[mid] - pfsum[left])\n            part2 = (pfsum[right + 1] - pfsum[mid]) - nums[mid] * (right - mid + 1)\n            return part1 + part2 <= k\n            \n        left = ans = 0\n        for right in range(n):\n            if check(left, right):\n                ans = max(ans, right - left + 1)\n            while not check(left, right):\n                left += 1\n        return ans\n```
['Python3']