Leetcode 3026. Maximum Good Subarray Sum
- Leetcode 3026. Maximum Good Subarray Sum
- 1. 解题思路
- 2. 代码实现
- 题目链接：3026. Maximum Good Subarray Sum
1. 解题思路
这一题的话主要就是要快速遍历所有的good subarray并快速获得每一个good subarray的和的最大值。
因此，问题就主要就成了两个问题：
- 如何快速找到所有的good subarray
- 对任意一个good subarray，如何快速求得其和
对于第二个问题，我们只需要用累积数组即可求得，对于任意一个已知首尾的subarray，我们将累积数组相减即可得到其对应的subarray的元素之和。
而对于第一个问题，我们只需要记录一下所有之前元素作为起始坐标时的位置即可。
更进一步地，由于我们只需要计算和的最大值，因此对于任意相同的元素作为开始坐标时，我们只需要保留其前部元素的最小值即可。
2. 代码实现
给出python代码实现如下：
class Solution:def maximumSubarraySum(self, nums: List[int], k: int) -> int:cumsums = list(accumulate(nums, initial=0))ans = -math.inf_min= {}def get_max_sub(s, tgt):return s - _min.get(tgt, math.inf)for i, x in enumerate(nums):s = cumsums[i+1]ans = max(ans, get_max_sub(s, x-k), get_max_sub(s, x+k))_min[x] = min(_min.get(x, math.inf), s-x)return ans if ans != -math.inf else 0
提交代码评测得到：耗时1093ms，占用内存30.6MB。