最大好子数组和

难度:

标签:

题目描述

You are given an array nums of length n and a positive integer k.

A subarray of nums is called good if the absolute difference between its first and last element is exactly k, in other words, the subarray nums[i..j] is good if |nums[i] - nums[j]| == k.

Return the maximum sum of a good subarray of nums. If there are no good subarrays, return 0.

Example 1:

Input: nums = [1,2,3,4,5,6], k = 1
Output: 11
Explanation: The absolute difference between the first and last element must be 1 for a good subarray. All the good subarrays are: [1,2], [2,3], [3,4], [4,5], and [5,6]. The maximum subarray sum is 11 for the subarray [5,6].

Example 2:

Input: nums = [-1,3,2,4,5], k = 3
Output: 11
Explanation: The absolute difference between the first and last element must be 3 for a good subarray. All the good subarrays are: [-1,3,2], and [2,4,5]. The maximum subarray sum is 11 for the subarray [2,4,5].

Example 3:

Input: nums = [-1,-2,-3,-4], k = 2
Output: -6
Explanation: The absolute difference between the first and last element must be 2 for a good subarray. All the good subarrays are: [-1,-2,-3], and [-2,-3,-4]. The maximum subarray sum is -6 for the subarray [-1,-2,-3].

Constraints:

2 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= k <= 10⁹

代码结果

运行时间: 183 ms, 内存: 28.5 MB

/*
题目思路：
1. 使用Java Stream来处理数组。
2. 遍历数组，寻找每个可能的子数组，判断其第一个和最后一个元素的差是否为k。
3. 如果是好子数组，计算其和并更新最大和。
4. 返回最大和，如果没有好子数组，返回0。
*/
import java.util.stream.IntStream;
public class Solution {
    public int maxGoodSubarraySum(int[] nums, int k) {
        int n = nums.length;
        return IntStream.range(0, n)
                .flatMap(i -> IntStream.range(i + 1, n)
                        .filter(j -> Math.abs(nums[i] - nums[j]) == k)
                        .map(j -> IntStream.rangeClosed(i, j).map(m -> nums[m]).sum()))
                .max()
                .orElse(0);
    }
}

解释

方法:

这个解决方案利用了前缀和和哈希表来查找符合条件的子数组和其最大和。前缀和用于计算从数组开始到当前位置的元素和，而哈希表用来存储每个遇到的元素的最小前缀和。对于数组中的每个元素，我们检查这个元素减去k以及加上k的值是否存在于哈希表中。如果存在，我们通过当前的前缀和减去哈希表中存储的前缀和，来计算可能的好子数组的和，并更新最大和。这样做可以有效地在一次遍历中找到满足条件的子数组并计算其和。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在解题策略中提到使用哈希表来存储每个元素的最小前缀和，这种方法能够处理所有元素都是负数的情况吗？

▷

是的，这个方法可以处理所有元素都是负数的情况。因为无论元素的符号如何，哈希表存储的是到当前元素为止的最小前缀和，这有助于计算任何子数组的和。在负数的情况下，最小前缀和将帮助我们找到可能的最大子数组和，因为从较小的负数前缀和到当前的前缀和的差值会较大，这正是我们想要最大化的值。

🦆

题解中的算法对于数组中存在重复元素时是否仍然有效？例如，如果数组中有两个相同的元素满足条件，算法是否能准确计算出最大的子数组和？

▷

是的，算法仍然有效，即使数组中有重复元素。算法使用哈希表存储每个元素值对应的最小前缀和，并在遍历过程中不断更新它。如果数组中有重复的元素，算法会考虑到每个重复元素的情况，并在计算子数组和时考虑到所有符合条件的子数组。因此，算法可以准确地计算出最大的子数组和，无论数组中是否包含重复元素。

🦆

为什么选择更新元素的最小前缀和而不是最大前缀和？更新最小前缀和在计算子数组的最大和时有什么优势？

▷

选择更新元素的最小前缀和而不是最大前缀和，是因为这样可以更有效地找到最大的子数组和。子数组的和可以通过当前前缀和减去之前的某个前缀和来计算。如果我们使用最小前缀和，那么当前前缀和减去最小前缀和将会给出可能的最大子数组和。反之，如果我们存储的是最大前缀和，那么计算出的子数组和会较小，无法达到寻找最大子数组和的目的。

🦆

在题解中，如果`num - k`和`num + k`不在哈希表中，解法似乎会错过一些潜在的好子数组。这种情况是如何避免的，或者说算法是如何确保不遗漏任何可能的好子数组的？

▷

实际上，如果`num - k`或`num + k`不在哈希表中，那么说明到目前为止还没有遇到能使得子数组和为k的元素。这意味着之前的元素和当前元素的组合不能形成好子数组。算法通过持续更新哈希表并检查每个元素时的条件来确保不遗漏任何可能的好子数组。虽然在某些情况下，初次遇到的`num - k`或`num + k`可能不在哈希表中，但这并不影响算法的有效性，因为对于每个新元素，只有在其相对应的`num - k`或`num + k`已经存在于哈希表中时，才可能形成好子数组。

最大好子数组和

题目描述

代码结果

解释

代码细节讲解

相关问题