processing of arrays
Given an array A. Find maximum length of sub-array with product of its elements being non zero.
Product of a sub-array will be zero if and only if it contains at least one zero element.
So we have to find out maximum size of the sub-array not containing zero.
So we can start processing the array from left to right and keep track of last position where we had found the zero element, at each step
we will compute the maximum size of the sub-array ending at the current position and not having any zeros in it (For i th element, the size of the sub-array will
be i - lastZeroIndex where lastZeroIndex is the index of the last zero found).
Finally we will take the maximum of all those values for each index i from 1 to N.
Please see the simple pseudo code.
lastZeroIndex = 0, ans = 0 for i = 1 to N: if a[i] == 0: lastZeroIndex = i cur = i - lastZeroIndex ans = max(ans, cur)
O(N), You just need a single pass of the array a.