class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
}
};
100183. 最大好子数组和
给你一个长度为 n 的数组 nums 和一个 正 整数 k 。
如果 nums 的一个子数组中，第一个元素和最后一个元素 差的绝对值恰好 为 k ，我们称这个子数组为 好 的。换句话说，如果子数组 nums[i..j] 满足 |nums[i] - nums[j]| == k ，那么它是一个好子数组。
请你返回 nums 中 好 子数组的 最大 和，如果没有好子数组，返回 0 。
示例 1：
输入：nums = [1,2,3,4,5,6], k = 1 输出：11 解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 1 。好子数组有 [1,2] ，[2,3] ，[3,4] ，[4,5] 和 [5,6] 。最大子数组和为 11 ，对应的子数组为 [5,6] 。
示例 2：
输入：nums = [-1,3,2,4,5], k = 3 输出：11 解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 3 。好子数组有 [-1,3,2] 和 [2,4,5] 。最大子数组和为 11 ，对应的子数组为 [2,4,5] 。
示例 3：
输入：nums = [-1,-2,-3,-4], k = 2 输出：-6 解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 2 。好子数组有 [-1,-2,-3] 和 [-2,-3,-4] 。最大子数组和为 -6 ，对应的子数组为 [-1,-2,-3] 。
提示：
2 <= nums.length <= 105-109 <= nums[i] <= 1091 <= k <= 109原站题解
java 解法, 执行用时: 71 ms, 内存消耗: 55.2 MB, 提交时间: 2024-02-04 17:50:51
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
long ans = Long.MIN_VALUE;
long sum = 0;
Map<Integer, Long> minS = new HashMap<>();
for (int x : nums) {
long s1 = minS.getOrDefault(x - k, Long.MAX_VALUE / 2);
long s2 = minS.getOrDefault(x + k, Long.MAX_VALUE / 2);
ans = Math.max(ans, sum + x - Math.min(s1, s2));
minS.merge(x, sum, Math::min);
sum += x;
}
return ans > Long.MIN_VALUE / 4 ? ans : 0;
}
}
golang 解法, 执行用时: 171 ms, 内存消耗: 12.5 MB, 提交时间: 2024-02-04 17:50:34
func maximumSubarraySum(nums []int, k int) int64 {
ans := math.MinInt
minS := map[int]int{}
sum := 0
for _, x := range nums {
s, ok := minS[x+k]
if ok {
ans = max(ans, sum+x-s)
}
s, ok = minS[x-k]
if ok {
ans = max(ans, sum+x-s)
}
s, ok = minS[x]
if !ok || sum < s {
minS[x] = sum
}
sum += x
}
if ans == math.MinInt {
return 0
}
return int64(ans)
}
python3 解法, 执行用时: 530 ms, 内存消耗: 34.4 MB, 提交时间: 2024-02-04 17:50:07
# 前缀和 + 哈希表
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
ans = -inf
min_s = defaultdict(lambda: inf)
s = 0
for x in nums:
ans = max(ans, s + x - min(min_s[x - k], min_s[x + k]))
min_s[x] = min(min_s[x], s)
s += x
return ans if ans > -inf else 0