子数组的最大频率分数

该题解采用滑动窗口的方法处理子数组的最大频率分数问题。首先，使用一个哈希表a_set记录窗口内各个数的出现次数。接着，定义一个变量now，用以计算当前窗口内各数值的幂和，其中幂的底为数值本身，指数为该数值在窗口中出现的次数，并对结果取一个大质数模以防溢出。初始化时，先处理前k个元素填充窗口，并计算这些元素构成的初始now值。随后，窗口向右滑动，每次移动时，更新哈希表和now值，即从now中减去滑出窗口的数的旧贡献值，并加上新进入窗口的数的新贡献值。同时，用max_ans记录遍历过程中的最大now值。最终，返回max_ans作为结果。

时间复杂度: O(n)

空间复杂度: O(k)

import collections
class Solution(object):
    def maxFrequencyScore(self, nums, k):
        n = len(nums) # 数组长度
        a_set = collections.defaultdict(int) # 记录窗口内数字出现频率
        for i in range(k): # 初始化窗口的频率表
            a_set[nums[i]] += 1
        now = 0 # 当前窗口的数值幂和
        base = 10 ** 9 + 7 # 防止溢出的大质数模
        for key, value in a_set.items(): # 计算初始窗口的now值
            now += pow(key, value, base)
        now %= base
        max_ans = now # 初始最大now
        for i in range(k, n): # 滑动窗口
            a_set[nums[i - k]] -= 1 # 更新窗口，移出一个元素
            val = a_set[nums[i - k]]
            now = now - pow(nums[i - k], val + 1, base) # 移出元素的旧贡献
            if val > 0:
                now += pow(nums[i - k], val, base) # 如果还在窗口内，加上新贡献
            a_set[nums[i]] += 1 # 新元素加入窗口
            val = a_set[nums[i]]
            now = now + pow(nums[i], val, base) # 新元素的贡献
            if val > 1:
                now -= pow(nums[i], val - 1, base) # 减去旧贡献
            now %= base
            max_ans = max(max_ans, now) # 更新最大now值
        return max_ans # 返回最大频率分数