# Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## Problem
Given an array `nums` and an integer `target`, return _the maximum number of **non-empty** **non-overlapping** subarrays such that the sum of values in each subarray is equal to_ `target`.

**Example 1:**

**Input:** nums = [1,1,1,1,1], target = 2
**Output:** 2
**Explanation:** There are 2 non-overlapping subarrays [**1,1**,1,**1,1**] with sum equals to target(2).

**Example 2:**

**Input:** nums = [-1,3,5,1,4,2,-9], target = 6
**Output:** 2
**Explanation:** There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

**Constraints:**

* `1 <= nums.length <= 105`
* `-104 <= nums[i] <= 104`
* `0 <= target <= 106`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem. We define `dp[i]` as the maximum number of non-overlapping subarrays with a sum equal to `target` that can be found in the suffix of the array starting from index `i`. The final answer will be `dp[0]`, which is computed by iterating backward through the array and considering all possible subarrays.
**Time:** O(N^2), where N is the length of `nums`. The nested loops (one for `i` and one for `j`) result in a quadratic time complexity. · **Space:** O(N), where N is the length of `nums`, for the `dp` array.
**Pros:** It is a straightforward and systematic way to explore all possibilities, guaranteeing an optimal solution.; The logic is relatively easy to understand for those familiar with dynamic programming.
**Cons:** The O(N^2) time complexity is inefficient for large inputs as specified by the constraints (N up to 10^5) and will likely result in a 'Time Limit Exceeded' error.
### Explanation
We build a `dp` array of size `n+1`, where `n` is the length of `nums`. `dp[i]` will store the result for the subarray `nums[i:]`. We initialize `dp[n]` to 0, as there are no subarrays in an empty array.

We iterate backward from `i = n-1` down to `0`. For each index `i`, we have two choices:
1.  **Don't start a subarray at index `i`**: In this case, the number of subarrays is the same as the number we can find starting from `i+1`, which is `dp[i+1]`. We set `dp[i] = dp[i+1]` as a baseline.
2.  **Start a subarray at index `i`**: We iterate with a second pointer `j` from `i` to `n-1`, calculating the sum of `nums[i...j]`. If this sum equals `target`, we have found a valid subarray. This gives us 1 subarray plus the maximum number of subarrays we can find in the rest of the array, which starts from index `j+1`. This value is `1 + dp[j+1]`. We then update `dp[i]` with the maximum value found among all such valid subarrays starting at `i`.

After the loops complete, `dp[0]` contains the maximum number of non-overlapping subarrays for the entire array.

```java
class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        
        for (int i = n - 1; i >= 0; i--) {
            // Option 1: Skip the element at index i
            dp[i] = dp[i + 1];
            
            long currentSum = 0;
            // Option 2: Find a subarray starting at i
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                if (currentSum == target) {
                    // Found a subarray nums[i...j].
                    // The result is 1 + max subarrays from index j+1.
                    dp[i] = Math.max(dp[i], 1 + dp[j + 1]);
                }
            }
        }
        
        return dp[0];
    }
}
```
### Algorithm
- Create a `dp` array of size `n + 1`, where `n` is the length of `nums`. Initialize all its values to 0.
- Iterate `i` from `n - 1` down to `0`:
  - First, assume we don't start a subarray at `i`. The result would be the same as for the subarray starting at `i+1`. So, set `dp[i] = dp[i + 1]`.
  - Initialize `current_sum = 0`.
  - Then, try to find a subarray starting at `i`. Iterate `j` from `i` to `n - 1`:
    - Add `nums[j]` to `current_sum`.
    - If `current_sum` equals `target`, we've found a valid subarray `nums[i...j]`.
    - This contributes 1 to the count, plus the maximum number of subarrays we can find in the remaining part of the array, which starts at index `j + 1`. This is given by `dp[j + 1]`.
    - Update `dp[i]` to be the maximum of its current value and `1 + dp[j + 1]`.
- The final answer is `dp[0]`, which represents the maximum number of subarrays for the entire array `nums[0...n-1]`.

## Greedy Approach with Prefix Sum
A more efficient approach is to use a greedy strategy combined with the prefix sum technique. The core idea is that whenever we find a subarray that sums to the target, we should commit to it and restart our search from the next element. This is because taking the earliest-ending subarray maximizes the length of the remaining array, thus maximizing the opportunity to find more non-overlapping subarrays. We can efficiently find these subarrays in linear time using a hash set to store prefix sums.
**Time:** O(N), where N is the length of `nums`. We iterate through the array only once, and `HashSet` lookups and insertions take, on average, O(1) time. · **Space:** O(N) in the worst case, where N is the length of `nums`. The `HashSet` could store up to N distinct prefix sums if no target-sum subarray is found and all prefix sums are unique.
**Pros:** Highly efficient with O(N) time complexity, making it suitable for large inputs.; The implementation is concise and elegantly combines the prefix sum technique with a greedy choice.
**Cons:** The correctness of the greedy strategy is not immediately obvious and relies on the insight that taking the shortest possible subarray is always optimal.; The space complexity is O(N) in the worst-case, which might be a concern for extremely memory-constrained environments, although it's generally acceptable.
### Explanation
We iterate through the array from left to right, maintaining a `current_prefix_sum`. We also use a `HashSet` to store the prefix sums encountered since the last found subarray (or from the beginning).

At each index `i`, we update `current_prefix_sum`. To check if a subarray ending at `i` has a sum of `target`, we need to see if `current_prefix_sum - target` exists in our set of previously seen prefix sums. This is based on the property that `sum(nums[j+1...i]) = prefix_sum[i] - prefix_sum[j]`. If we want this sum to be `target`, we need to find a `j` such that `prefix_sum[j] = current_prefix_sum - target`.

If we find such a prefix sum in our set, we've found a valid subarray. Following the greedy strategy, we increment our count of non-overlapping subarrays. Then, to ensure the next subarray we find is non-overlapping, we 'reset' our search. This is done by clearing the `HashSet` and re-initializing it with just `0` (to handle subarrays that start from the next element). We also effectively reset the `current_prefix_sum` to 0 relative to the new starting point.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        // Use a set to store prefix sums encountered in the current search window.
        Set<Long> seenSums = new HashSet<>();
        // Add 0 to handle subarrays that start from the beginning of a search segment.
        seenSums.add(0L); 
        
        int count = 0;
        long currentSum = 0;
        
        for (int num : nums) {
            currentSum += num;
            if (seenSums.contains(currentSum - target)) {
                // Found a subarray with the target sum.
                count++;
                // Reset for the next non-overlapping subarray search.
                currentSum = 0;
                seenSums.clear();
                seenSums.add(0L);
            } else {
                // Add the current prefix sum to the set for future checks.
                seenSums.add(currentSum);
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0` and `prefix_sum = 0`.
- Create a `HashSet` called `seen_sums` and add `0` to it. This initial `0` is crucial for finding subarrays that start at the beginning of a search segment.
- Iterate through each number `num` in the `nums` array:
  - Update `prefix_sum` by adding `num` to it.
  - Check if `prefix_sum - target` exists in `seen_sums`.
    - If it exists, it means we have found a subarray ending at the current position with the desired sum.
      - Increment `count`.
      - To ensure the next subarray is non-overlapping, we must reset our search. Set `prefix_sum = 0`, clear `seen_sums`, and add `0` back to it.
    - If it does not exist, it means no subarray ending at the current position sums to `target`.
      - Add the current `prefix_sum` to `seen_sums` to be used for future checks.
- After iterating through the entire array, return `count`.

# Solutions
### Java

```java
class Solution { public int maxNonOverlapping ( int [] nums , int target ) { int ans = 0 , n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { Set < Integer > vis = new HashSet <>(); int s = 0 ; vis . add ( 0 ); while ( i < n ) { s += nums [ i ]; if ( vis . contains ( s - target )) { ++ ans ; break ; } ++ i ; vis . add ( s ); } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  int maxNonOverlapping(vector<int> &nums, int target) {
    int ans = 0, n = nums.size();
    for (int i = 0; i < n; ++i) {
      unordered_set<int> vis{{0}};
      int s = 0;
      while (i < n) {
        s += nums[i];
        if (vis.count(s - target)) {
          ++ans;
          break;
        }
        ++i;
        vis.insert(s);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int: ans = 0 i, n = 0, len(nums) while i < n: s = 0 vis = {0} while i < n: s += nums[i] if s - target in vis: ans += 1 break i += 1 vis . add(s) i += 1 return ans

```