Sliding Window | Understand the Absolute Value and Median
Intuition\n Describe your first thoughts on how to solve this problem. \nThe idea is similar to the 2967. These two problems in the contest both need to use the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe idea is similar to the 2967. These two problems in the contest both need to use the median and absolute value.\n\nFor sliding window `[l, r]`, the best choice to make the numbers in this range equal is to make them all equal to the median in this range.\n\nThe median index is `(l + r + 1) / 2`, and you can find when we add a new right point `nums[r]`, the cost of making all numbers equal in the window adds `nums[r] - nums[old_median]`. When we remove `nums[l]`, the cost reduces `nums[old_median] - nums[l]`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n logn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1) (or O(log n) used in sorting)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int maxFrequencyScore(int[] nums, long k) {\n        Arrays.sort(nums);\n        int left = 0, maxFreq = 1;\n        long cost = 0;\n        int med = 0;\n        for (int right = 1; right < nums.length; right++) {\n            cost += nums[right] - nums[med];\n            med = (left + right + 1) / 2;\n            while (cost > k) {\n                cost -= nums[med] - nums[left];\n                left++;\n                med = (left + right + 1) / 2;\n            }\n\n            maxFreq = Math.max(maxFreq, right - left + 1);\n        }\n\n        return maxFreq;\n    }\n}\n```
['Java']