To solve this problem, we need to find the maximum number of non-overlapping subarrays with a sum of zero in a given array of integers.

Approach

The key insight here is to use a hash set to track the prefix sums of the current window. When we encounter a prefix sum that we've seen before, it indicates that the subarray between the previous occurrence of this sum and the current index has a sum of zero. Once we find such a subarray, we reset our tracking variables to start looking for the next non-overlapping subarray.

Steps:

1. Initialize Variables:

   • current_sum to keep track of the sum of elements from the start of the current window.
   • count to count the number of non-overlapping zero-sum subarrays.
   • prefix_set to store the prefix sums of the current window (initialized with 0 to handle cases where the subarray starts from the beginning).

2. Iterate Through the Array:

   • For each element, add it to current_sum.
   • If current_sum is present in prefix_set, increment the count (since we found a zero-sum subarray), then reset current_sum and prefix_set to start tracking the next window.
   • If current_sum is not present in prefix_set, add it to the set.

Solution Code

def max_non_overlapping_zero_sum_subarrays(arr):
    current_sum = 0
    count = 0
    prefix_set = set()
    prefix_set.add(0)  # To handle subarrays starting from index 0

    for num in arr:
        current_sum += num
        if current_sum in prefix_set:
            count += 1
            # Reset for next non-overlapping subarray
            current_sum = 0
            prefix_set = set()
            prefix_set.add(0)
        else:
            prefix_set.add(current_sum)

    return count

Explanation

• Prefix Sum Tracking: The prefix sum helps us quickly identify subarrays with sum zero. If the same prefix sum occurs again, the subarray between these two indices has a sum of zero.
• Non-overlapping: By resetting the current_sum and prefix_set after finding a zero-sum subarray, we ensure that the next subarray we find does not overlap with the previous one.
• Edge Cases: Handles cases like arrays with multiple zeros (each zero is a valid subarray) and subarrays starting from the first element.

This approach efficiently finds the maximum number of non-overlapping zero-sum subarrays with a time complexity of O(n) (since each element is processed once and set operations are O(1) average case). The space complexity is O(n) in the worst case, where no zero-sum subarrays are found and all prefix sums are stored.

Example: For the array [1, -1, 2, -2, 3, -3], the function returns 3 (the subarrays are [1,-1], [2,-2], [3,-3]). For the array [0,0,0], it returns 3 (each zero is a subarray). For [1,2,-3,3,-1,2,-2], it returns 2 (subarrays [1,2,-3] and [3,-1,2,-2]).

This solution is optimal and handles all possible cases correctly.

作者声明:本文包含人工智能生成内容。