Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum?
Yes, by using dynamic programming we can do that. Take an array which is of same size. We can find this in n iterations.
In the first iteration, we find the length of longest sub sequence with zero sum beginning with the first element.
In the second iteration, we find the length of longest sub sequence with zero sum beginning with second element and so on.
Let us calculate this array for the above example
Iteration 1:
Cumulative Sum = 5 5 4 7 5 9
Max Length = 0 0 0 0 0 0
For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements.
The straight forward approach is to check the sum of all possible arrays and find out the maximum length sub array. This will run in O(n3) time.
Can we do better than this?
Yes, by using dynamic programming we can do that. Take an array which is of same size. We can find this in n iterations.
In the first iteration, we find the length of longest sub sequence with zero sum beginning with the first element.
In the second iteration, we find the length of longest sub sequence with zero sum beginning with second element and so on.
Let us calculate this array for the above example
Iteration 1:
Cumulative Sum = 5 5 4 7 5 9
Max Length = 0 0 0 0 0 0
Iteration 2:
Cumulative Sum = _ 0 -1 2 0 4
Max Length = 0 1 0 0 4 0
Iteration 3:
Cumulative Sum = _ _ -1 2 0 4
Max Length = 0 1 0 0 4 0
and so on.
At the end of all this, maximum of this array contains the result.
Here is the C++ code.