[C++] Sliding Window with Prefix Sum
Intuition\n Describe your first thoughts on how to solve this problem. \n- The cost to set nums[l], ..., nums[m], ..., nums[r] to nums[m], ..., nums[m], ..., nu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- The cost to set `nums[l], ..., nums[m], ..., nums[r]` to `nums[m], ..., nums[m], ..., nums[m]` is\n  - `leftCost = COUNT(left) * nums[m] - SUM(left)`\n    - where `left` is `nums[l], ... , nums[m - 1]`\n  - `rightCost = SUM(right) - COUNT(right) * nums[m]`\n    - where `right` is `nums[m + 1], ... nums[r]`\n- We can use the prefix sum to speed up the `SUM()` operations on the above\n- Use sliding window to maximize the window width and meet the condition `cost < k`\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Sort the array\n- Calculate prefix sum\n- Sliding window with dynamic width\n  - Shrink the window width if we don\'t meet the condition\n\n# Complexity\n- Time complexity: $$O({n}\\times{\\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 {\npublic:\n    // time/space: O(nlogn)/O(n)\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        // sort the array\n        sort(nums.begin(), nums.end());\n\n        // calculate prefix sum\n        int n = nums.size();\n        vector<long long> prefix(n + 1, 0LL);\n        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];\n\n        // sliding window with dynamic width\n        int maxScore = 0;\n        for (int l = 0, r = 0; r < n; r++) {\n            // shrink the window width if we don\'t meet the condition\n            while (getCost(nums, prefix, l, r) > k) l++;\n            maxScore = max(maxScore, r - l + 1);\n        }\n        return maxScore;\n    }\nprivate:\n    long long getCost(vector<int>& nums, vector<long long>& prefix, int l, int r) {\n        int m = l + (r - l + 1) / 2;\n        long long costLeft = (long long)(m - l) * nums[m] - (prefix[m] - prefix[l]);\n        long long costRight = (prefix[r + 1] - prefix[m + 1]) - (long long)(r - m) * nums[m];\n        return costLeft + costRight;\n    }\n};\n```
['Two Pointers', 'Sliding Window', 'Prefix Sum', 'C++']