Sliding window
Intuition\n\nThe problem is to find the largest subset of indices, say $I$, such that for some $c$: \n\n\sum_{i\in I} |\text{nums}i-c|\leq k.\n\nSince the absol
# Intuition\n\nThe problem is to find the largest subset of indices, say $I$, such that for some $c$: \n$$\n\\sum_{i\\in I} |\\text{nums}_i-c|\\leq k.\n$$\nSince the absolute error is minimized at the median, it is enough to consider only the median value for $c$. \n\nMedian and the absolute error are easily computed if the numbers are sorted. It is also easy to see that after sorting the subset of indices $I$ must be of the form $[\\text{left}, \\text{right})$. For a given interval $[a,b)$ the sum in question is\n$$\n\\begin{aligned}\n\\text{value}(a,b) &\n= \\min_{c}\\sum_{a\\leq i < b} |\\text{nums}_i-c| \\\\\n&=(S_b-S_{m})-(b-m)c + (m-a) c- (S_m-S_a)\n\\end{aligned} \n$$\nwhere $m = (a+b)//2$, $S_i = \\sum_{j<i} \\text{nums}_j$.\n \nTo get the largest interval $[a, b)$ such that its value is not greater than $k$ one can slide a window through the array, whose width is the maximal frequency found so far. If moving `right` to the next position does not violate the condition `left` is kept unchanged, otherwise it is moved to its next position as well.\n\n# Complexity\n- Time complexity: $$O(n\\log(n))$$ (sorting).\n\n- Space complexity: $$O(n)$$ (for the precomputed sum values).\n\n# Code\n```\nclass Solution:\n    def maxFrequencyScore(self, nums: List[int], k: int) -> int:\n        nums.sort()\n        sum_vals = [0]+list(accumulate(nums))\n        left = 0\n        for right in range(1, len(sum_vals)):\n            mid = (right+left)//2\n            val = (sum_vals[right]-sum_vals[mid]) - (right-mid)*nums[mid]\n            val += (mid-left)*nums[mid] - (sum_vals[mid]-sum_vals[left])\n            if val > k:\n                left += 1\n        return right-left\n```
['Python3']