Problem Explanation

Given an array of integers nums and an integer target, the problem is to find the maximum number of non-overlapping sub-arrays that sum up to target.

A sub-array is a contiguous part of an array, and two sub-arrays are said to be overlapping if they share at least one index. We need to find the maximum amount of non-overlapping(sub-arrays do not share any index) sub-arrays that sum up to target.

The solution employs a greedy approach, meaning we always make the choice that seems to be the best at that moment. If we target is found in prefix sum array we reset prefix sum to zero so that next search starts from zero. Unordered_set is used because it allows for faster look-up times compared to other data structures.

If prefix[0, i] - target(our sum) exists in prefix records, then it indicates there exists a subarray which sums up to target, and we increment our answer, reset prefix to 0 and reset the prefixes set.

Solution

Python

1
2python
3class Solution:
4    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
5        prefix_sum = {0}
6        prefix = 0
7        ans = 0
8        for num in nums:
9            prefix += num
10            if prefix - target in prefix_sum:
11                ans += 1
12                prefix = 0
13                prefix_sum = {0}
14            else:
15                prefix_sum.add(prefix)
16        return ans

Java

1
2java
3class Solution {
4    public int maxNonOverlapping(int[] nums, int target) {
5        Set<Integer> prefixSet = new HashSet<>();
6        prefixSet.add(0);
7        int ans = 0, prefix = 0;
8        for (int num : nums) {
9            prefix += num;
10            if (prefixSet.contains(prefix - target)) {
11                ans++;
12                prefix = 0;
13                prefixSet = new HashSet<>(); 
14                prefixSet.add(0);
15            } else {
16                prefixSet.add(prefix);
17            }
18        }
19        return ans;
20    }
21}

Javascript

1
2javascript
3var maxNonOverlapping = function(nums, target) {
4    let prefixSet = new Set([0]);
5    let ans = 0, prefix = 0;
6    for (let num of nums) {
7        prefix += num;
8        if (prefixSet.has(prefix - target)) {
9            ans++;
10            prefix = 0;
11            prefixSet = new Set([0]);
12        } else {
13            prefixSet.add(prefix);
14        }
15    }
16    return ans;
17};

C++

1
2c++
3class Solution {
4public:
5    int maxNonOverlapping(vector<int>& nums, int target) {
6        unordered_set<int> prefixSet {0};
7        int prefix = 0, ans = 0;
8        for (auto num : nums) {
9            prefix += num;
10            if (prefixSet.count(prefix - target)) {
11                ans++;
12                prefix = 0;
13                prefixSet = {0};
14            } else {
15                prefixSet.insert(prefix);
16            }
17        };
18        return ans;
19    }
20};

C#

1
2csharp
3public class Solution {
4    public int MaxNonOverlapping(int[] nums, int target) {
5        var prefixSet = new Set<int>() {0};
6        int ans = 0, prefix = 0;
7        foreach (int num in nums) {
8            prefix += num;
9            if (prefixSet.Contains(prefix - target)) {
10                ans++;
11                prefix = 0;
12                prefixSet = new Set<int>() {0};
13            } else {
14                prefixSet.Add(prefix);
15            }
16        }
17        return ans;
18    }
19}

If we see a prefix that we've seen before, then there must exist a subarray in between these two prefixes that add up to 0. Because removing this subarray will not change the total sum of all numbers.+This concept is at the very core of the solution. By keeping a record of all previously observed prefixes, we can quickly identify when a subarray has summed up to our target. The use of a set data structure to store these prefixes proves very useful, thanks to its efficient look-up times.

The occurrence of a previously seen prefix indicates that a whole subarray has summed up to the target, and hence we can increment the result counter. The greedy part of the solution is resetting the prefix and the prefix records whenever we identify a valid subarray that sums to the target. This is because we want to maximize the number of non-overlapping subarrays, and since we have already used the elements of the existing subarray, we reset the prefix and prefix records to start anew.

Remember, a greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. We make the best choice at the moment to get the optimal solution of the complete problem.

In conclusion, the solution for finding the maximum number of non-overlapping subarrays that sum up to a given target is elegantly solved by using a greedy approach, storing prefix sums in a set for quick look-ups, and resetting the prefix and prefix set whenever a valid subarray is identified. It’s a great display of how patterns can be recognized and efficiently handled with the right data structures and algorithms. The solution holds for several languages including Python, Java, JavaScript, C++, and C# that rely on same algorithm and approach.