Computing maximum length subarray that sums to 0 →
In a previous post we saw how to compute all the subarrays (formed by consecutive elements of an array) that sum to zero. Here, we are going to compute the maximum length one among all those subarrays. You might think why it needs a separate post - one can store all the computed subarrays in a vector and find the maximum of the sizes of the vectors. But one could in fact keep track of the maximum length as and when we compute the individual subarrays that sum to zero.
Let us look at the naïve approach, as it would be much simpler to understand, and incorporate this computation into it.
We initialized a variable max_len
to 0
and update it as and when we find the starting and ending indices of the subarray that sums to zero. We can extend the same idea to the linear scan algorithm, as below: