C++ Sliding Window [PrefixSum + Median]
Complexity
Time complexity:  O(nlog(n))

Space complexity:  O(n)
Code

# Complexity
- Time complexity:  $$O(nlog(n))$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:  $$O(n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
#define ll long long
class Solution {
public:
    int maxFrequencyScore(vector<int>& nums, ll k) {
        sort(nums.begin(), nums.end());  // Sort in ascending order
        int n = nums.size();
        
        vector<ll> prefix(n + 1, 0);  // Prefix sum array
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        ll start = 0, ans = 0;
        for (ll end = 0; end < n; end++) {
            ll len = end - start + 1;
            ll median = nums[(start + end) / 2];  // Find the median
            
            // Compute the cost of making all elements in the window equal to median
            ll midIdx = (start + end) / 2;
            ll leftSum = prefix[midIdx + 1] - prefix[start];  // Sum of left half
            ll rightSum = prefix[end + 1] - prefix[midIdx + 1];  // Sum of right half
            
            ll krem = k - ((median * (midIdx - start + 1) - leftSum) + 
                           (rightSum - median * (end - midIdx)));

            while (start <= end && krem < 0) {
                start++;  // Shrink window from left
                len = end - start + 1;
                
                midIdx = (start + end) / 2;
                median = nums[midIdx];

                leftSum = prefix[midIdx + 1] - prefix[start];
                rightSum = prefix[end + 1] - prefix[midIdx + 1];

                krem = k - ((median * (midIdx - start + 1) - leftSum) + 
                            (rightSum - median * (end - midIdx)));
            }

            ans = max(ans, len);  // Update max frequency
        }
        
        return ans;
    }
};

```
['C++']