Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Intuition

A subarray from j+1 to i sums to target exactly when prefix[i] - prefix[j] equals target, i.e. prefix[i] - target equals some earlier prefix. To maximize disjoint pieces, we should close a subarray as early as possible, because an earlier cut never hurts future choices. So we keep a set of prefix sums observed since the previous cut, and the instant currentPrefix - target is present in that set we claim a subarray. After claiming, we clear the set and treat the position right after the cut as a fresh start (prefix reset to 0). This greedy leaves the largest possible tail available for more subarrays.

Algorithm walkthrough

1. 1Initialize a running prefix sum of 0 and a set seeded with the value 0 (the empty prefix).
2. 2Walk through the array, adding each element to the running prefix.
3. 3Check whether prefix - target already exists in the set; if so a valid subarray ends here.
4. 4On a hit, increment the answer, reset the prefix to 0, and reset the set to just {0} so the next window starts fresh after the cut.
5. 5Otherwise insert the current prefix into the set and keep scanning.
6. 6Return the accumulated count once the scan completes.

Implementation

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        count = 0
        prefix = 0
        seen = {0}
        for num in nums:
            prefix += num
            if prefix - target in seen:
                count += 1
                prefix = 0
                seen = {0}
            else:
                seen.add(prefix)
        return count