To solve this problem, we need to find the maximum number of non-overlapping subarrays with a sum of zero. The key insight here is to use a hash map to track prefix sums and identify zero-sum subarrays efficiently.

Approach

1. Prefix Sum Tracking: We use a prefix sum to keep track of the cumulative sum of elements up to the current index. If the same prefix sum is encountered again, the subarray between these two indices has a sum of zero.
2. Non-overlapping Subarrays: Once we find a zero-sum subarray, we reset our prefix sum and the hash map to start tracking from the next index, ensuring non-overlapping subarrays.
3. Hash Map Initialization: We initialize the hash map with {0: -1} to handle the case where the subarray starts from the first index (sum of elements from index 0 to current index is zero).

Solution Code

def max_zero_subarrays(arr):
    current_sum = 0
    count = 0
    prefix_map = {0: -1}  # Initialize with prefix sum 0 at index -1

    for i in range(len(arr)):
        current_sum += arr[i]

        if current_sum in prefix_map:
            # Found a zero-sum subarray
            count += 1
            # Reset to start tracking next non-overlapping subarray
            current_sum = 0
            prefix_map = {0: -1}
        else:
            # Store the current prefix sum and its index
            prefix_map[current_sum] = i

    return count

Explanation

1. Initialization: We start with current_sum set to 0, count set to 0, and prefix_map initialized with {0: -1}.
2. Iterate Through Array: For each element in the array, we update the current_sum by adding the element.
3. Check for Zero Sum: If current_sum is already in prefix_map, it means we have found a zero-sum subarray. We increment the count, reset current_sum to 0, and reset the prefix_map to start tracking from the next index.
4. Store Prefix Sum: If current_sum is not in the map, we store it along with its index.

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 space complexity of O(n) (for the hash map, though it is reset after each zero-sum subarray, so in practice it's lower for many cases).

Examples:

• Input: [1, -1, 2, -2, 3, -3] → Output: 3 (subarrays: [1,-1], [2,-2], [3,-3]).
• Input: [0,0,0] → Output: 3 (each 0 is a valid subarray).
• Input: [1,2,-3,3] → Output: 1 (subarray [1,2,-3]).

This solution handles all edge cases and provides an optimal way to solve the problem.

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