2524. Maximum Frequency Score of a Subarray
You are given an integer array nums and a positive integer k.
The frequency score of an array is the sum of the distinct values in the array raised to the power of their frequencies, taking the sum modulo 10^9 + 7.
- For example, the frequency score of the array
[5,4,5,7,4,4] is (4^3 + 5^2 + 7^1) modulo (10^9 + 7) = 96.
Return the maximum frequency score of a subarray of size k in nums. You should maximize the value under the modulo and not the actual value.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,1,1,2,1,2], k = 3
Output: 5
Explanation: The subarray [2,1,2] has a frequency score equal to 5. It can be shown that it is the maximum frequency score we can have.
Example 2:
Input: nums = [1,1,1,1,1,1], k = 4
Output: 1
Explanation: All the subarrays of length 4 have a frequency score equal to 1.
Constraints:
1 <= k <= nums.length <= 10^51 <= nums[i] <= 10^6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <iostream>
#include <vector>
#include <map>
const int M = 1000000007;
class Solution {
public:
int maxFrequencyScore(std::vector<int>& nums, int k) {
std::unordered_map<int, int> map;
int n = nums.size();
k = std::min(n, k);
long long sum = 0;
for (int i = 0; i < k; ++i) {
sum = (sum + diff(map, nums[i])) % M;
++map[nums[i]];
}
long long max_sum = sum;
for (int i = k; i < n; ++i) {
--map[nums[i - k]];
sum = (sum + M - diff(map, nums[i - k]) + diff(map, nums[i])) % M;
++map[nums[i]];
max_sum = std::max(max_sum, sum);
}
return max_sum;
}
private:
long long pow_(long long base, long long exp_, long long mod) {
long long res = 1;
base = base % mod;
while (exp_ > 0) {
if (exp_ % 2 == 1) {
res = (res * base) % mod;
}
base = (base * base) % mod;
exp_ /= 2;
}
return res;
}
int diff(std::unordered_map<int, int>& map, int num) {
long long diff;
if (map[num] == 0) {
diff = num % M;
}
else {
diff = (M - pow_(num, map[num], M) + pow_(num, map[num] + 1, M)) % M;
}
return diff;
}
};
|
