3026. 最大好子数组和（Rating 1816）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

3026. 最大好子数组和

Rating 1816

思路

子数组和一般都要通过计算前缀和来快速计算。

对于与当前num差为k的数字的下标，可以用哈希表维护。

但遍历num时，再遍历与num差k的数字的下标，时间复杂度就超了。

看题目的例子，数组既不是有序的，也含有负数，因此二分也是不行的。

于是卡住了。。。

学习灵神的题解后，关键思路在于

遍历num时，如果需要子数组的和最大，则需要num + k或num - k对应数字的前缀和最小，而这个可以通过哈希表去维护，问题迎刃而解。

后面遇到类似的题目一定要学会像灵神这样推导

如果推导后可以将表达式表示为仅与当前下标有关时，就可以利用哈希表解决类似问题。

代码

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        mp = defaultdict(lambda: inf) # 使用hash表维护每个num对应的前缀和（不含num本身）的最小值，默认inf
        pres = [0 for _ in range(len(nums) + 1)] # 前缀和
        ret = -inf # 答案
        for idx, num in enumerate(nums):
            pres[idx + 1] = pres[idx] + num # 维护前缀和
            ret = max(ret, pres[idx + 1] - mp[num + k]) # 计算num + k答案
            ret = max(ret, pres[idx + 1] - mp[num - k]) # 计算num - k答案
            mp[num] = min(mp[num], pres[idx]) # 更新mp
        return ret if ret > -inf else 0

因为可以一遍遍历，前缀和数组可以简化为滚动数组。

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        mp = defaultdict(lambda: inf)
        pres = 0
        ret = -inf
        for idx, num in enumerate(nums):
            ret = max(ret, pres + num - mp[num + k])
            ret = max(ret, pres + num - mp[num - k])
            mp[num] = min(mp[num], pres)
            pres += num
        return ret if ret > -inf else 0