[Java/C++/Python] Sliding Window, no Binary Search
Intuition\nSort the input A,\nand we will make a subarray of A all same,\nwith cost at most k.\n\nthe cost of making subarray same,\nis the bigger half sum - sm
# **Intuition**\nSort the input `A`,\nand we will make a subarray of `A` all same,\nwith cost at most `k`.\n\nthe cost of making subarray same,\nis the bigger half sum - smaller half sum.\n<br>\n\n\n# **Solution 1: With Binary Search**\n\nBinary search the length of subarray,\nand one pass `A` to check if it\'s possible.\n\nTime `O(nlogn)`\nSpace `O(n)`\n\n**Python**\n```py\n    def maxFrequencyScore(self, A: List[int], k: int) -> int:\n        n = len(A)\n        acc = list(accumulate(sorted(A), initial = 0))\n        l, r = 1, n\n        while l < r:\n            m = (l + r + 1) // 2\n            for i in range(n - m + 1):\n                if (acc[i + m] - acc[i + (m + 1) // 2]) - (acc[i + m // 2] - acc[i]) <= k:\n                    l = m\n                    break\n            else:\n                r = m - 1\n        return l\n```\n<br>\n\n# **Solution 2: Sliding Window**\nActually in solution,\nwe already keep(calculate) the cost of sliding window,\nWe don\'t need to binary search the window size.\n\nSo we apply a normal sliding window format to solve this problem,\n`cur` means the cost of current sliding window.\n\nTime `O(sort)`\nSpace `O(sort)`\n\n**Java**\n```java\n    public int maxFrequencyScore(int[] A, long k) {\n        int i = 0, res = 0, n = A.length;\n        long cur = 0;\n        Arrays.sort(A);\n        for (int j = 0; j < n; ++j) {\n            cur += A[j] - A[(i + j) / 2];\n            while (cur > k) {\n                cur -= A[(i + j + 1) / 2] - A[i];\n                i++;\n            }\n            res = Math.max(res, j - i + 1);\n        }\n        return res;\n    }\n```\n<br>\n\n# **Solution 3: Shorter Version**\nAdvanced shorter version of sliding window.\n`O(sort)` for sort\nTime `O(n)` for sliding window\nSpace `O(1)` for sliding window\n\n**Java**\n```java\n    public int maxFrequencyScore(int[] A, long k) {\n        int i = 0, n = A.length;\n        Arrays.sort(A);\n        for (int j = 0; j < n; ++j)\n            if ((k -= A[j] - A[(i + j) / 2]) < 0)\n                k += A[(i + j + 1) / 2] - A[i++];\n        return n - i;\n    }\n```\n\n**C++**\n```cpp\n    int maxFrequencyScore(vector<int>& A, long long k) {\n        int i = 0, n = A.size();\n        sort(A.begin(), A.end());\n        for (int j = 0; j < n; ++j)\n            if ((k -= A[j] - A[(i + j) / 2]) < 0)\n                k += A[(i + j + 1) / 2] - A[i++];\n        return n - i;\n    }\n```\n**Python**\n```py\n    def maxFrequencyScore(self, A: List[int], k: int) -> int:\n        i = 0\n        A.sort()\n        for j in range(len(A)):\n            k -= A[j] - A[(i + j) // 2]\n            if k < 0:\n                k += A[(i + j + 1) // 2] - A[i]\n                i += 1\n        return j - i + 1\n```\n
['C', 'Python', 'Java']