An array contains both positive and negative elements, find the largest subarray whose
sum equals 0.

**Example**
int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}

int output = {4, 6, 3, -9, -5, 1} of length 6

###
Solution

Method 1 - Brute force

**Method 2 - Storing the sum in temp array**
Given an

`int[] input`

array, you can create an

`int[] tmp`

array where

` `

`tmp[i] = tmp[i - 1] + input[i];`

Each element of tmp will store the sum of the input up to that element.

Example

int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}

int[] tmp = {4, 10, 13, 4, -1, 0, 3, 3, 5}

Now if you check tmp, you'll notice that there might be values that are equal to each other.For example, take the element 4 at index 0 and 3, element 3 at index 6 and 7. So, it means sum between these 2 indices has remained the same, i.e. all the elements between them add upto 0. So, based on that we get {6, 3, -9} and {0}.

Also, we know tmp[-1] = 0. When we have not started the array we have no element added to it. So, if we find a zero inside the tmp array, that means all the numbers starting 0th index to 5th index(where 0 exists in temp) are all 0s, so our subarray becomes {4,6,3, -9,-5,1}.

Out of {6, 3, -9}, {0} and {4,6,3, -9,-5,1}, last one is our answer as it is the largest sub array.

__To sum it up__
We notice that some values are same in tmp array. Let's say that this values are at indexes

`j an k with j < k`

, then the sum of the input till

`j`

is equal to the sum till

`k`

and this means that the sum of the portion of the array between

`j`

and

`k`

is 0! Specifically the 0 sum subarray will be from index j + 1 to k.

- NOTE: if
`j + 1 == k`

, then `k is 0`

and that's it! ;)
- NOTE: The algorithm should consider a virtual
`tmp[-1] = 0`

;
- NOTE: An empty array has sum 0 and it's minimal and this special
case should be brought up as well in an interview. Then the interviewer
will say that doesn't count but that's another problem! ;)