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]).

·
Santiago Trujillo