Prefix Sum + Binary Search
Intuition\nLet\'s cosider the cost, to make all the elements of the array $[a_0, a_1, ..., a_{n - 1}]$ are equal to $x$, as:\n\n$S = |a_0 - x| + |a_1 - x| + ...
# Intuition\nLet\'s cosider the cost, to make all the elements of the array $[a_0, a_1, ..., a_{n - 1}]$ are equal to $x$, as:\n\n$S = |a_0 - x| + |a_1 - x| + ... + |a_{n-1} - x|$\n\nThis value is minimum if $x$ is the element of this array, located at the median. \n\nThe proof is here: https://leetcode.com/problems/minimum-cost-to-make-array-equalindromic/solutions/4418867/backtracking/\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1) Pre calculate prefix sum array $s$ of the $nums$ array in $O(n)$ time, where $n$ is the length of the $nums$ array\n2) Using binary search find the maximum length of the sub array where all elements are equalized using at most $k$ operations in $O(logn)$ time\n3) For each of this sub array search is there exist a sub array where all elements are equalized using at most $k$ operations in at most $O(n)$ time, i.e. for each $i = [1..n - m]$ we need to check $s[j] - s[(j + i) / 2] - s[(j + i - 1) / 2] + s[i - 1] \\le k$, where $m$ is the length of the sub array and $j = i + m$\n4) So the total time is $O(n + n*logn) = O(n*logn)$\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(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nwhere $n$ is the length of the $nums$ array.\n\n# Code\n```\nimpl Solution {\n    pub fn max_frequency_score(mut nums: Vec<i32>, mut k: i64) -> i32 {\n        let n = nums.len();\n\n        nums.sort_unstable();\n\n        let mut s = vec![0; n + 1];        \n\n        for i in 0..n {\n            s[i + 1] = s[i] + nums[i] as i64;\n        }\n\n        let mut l = 1;\n        let mut r = n;\n\n        while l < r {\n            let m = (l + r + 1) / 2;\n\n            for i in 0..n - m + 1 {\n                if s[i + m] - s[(2*i + m + 1) / 2] - s[(2*i + m) / 2] + s[i] <= k {\n                    l = m;\n                    break;\n                }\n            }\n\n            if l < m {\n                r = m - 1;\n            }\n        }\n\n        l as i32\n    }    \n}\n```
['Rust']