title: Maximum number of subarrays having equal sum
body: <p>I was asked this question in one of my interview. Given an array of integers (<strong>with both positive and negative values</strong>) we need to find the <strong>maximum number of disjoint subarrays having equal sum</strong>.</p>
  <p><strong>Example :</strong></p>
  <p>Input : [1, 2, 3]
  Output : 2 {since we have at most 2 subarrays with sum = 3 i.e. [1, 2],[3]}</p>
  <p>Input: [2 2 2 -2]
  Output : 2 {two subarrays each with sum = 2 i.e. [2],[2, 2, -2]}</p>
  <p><strong>My Approach</strong></p>
  <p>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] .</p>
  <p>But this failed in the case of negative numbers. How to handle the negative cases?</p>
  <p><strong>EDIT</strong> Complete array must be covered with these subarrays. That is why in example 2 we get <strong>2</strong> as output and not 3 ([2],[2],[2]).</p>