I was asked this question in one of my interview. Given an array of integers (with both positive and negative values) we need to find the maximum number of disjoint subarrays having equal sum.

Example :

Input : [1, 2, 3] Output : 2 {since we have at most 2 subarrays with sum = 3 i.e. [1, 2],[3]}

Input: [2 2 2 -2] Output : 2 {two subarrays each with sum = 2 i.e. [2],[2, 2, -2]}

My Approach

First approach that came to my mind was to find the prefix sum array and then taking each element (prefix[i]) as target finding the number of subarrays with sum = prefix[i] .

But this failed in the case of negative numbers. How to handle the negative cases?

EDIT Complete array must be covered with these subarrays. That is why in example 2 we get 2 as output and not 3 ([2],[2],[2]).