# Find position in array where element-wise multiplication with string of 1 and 0s results in max value

I have a sequence of 1s and 0s. For example: $$bits = [1, 0, 1, 1, 1, 0]$$. I also have an array of positive integers. For example $$arr = [12, 23, 4, 6, 8, 0, 24, 72]$$. I need to find the index, $$i$$, in $$arr$$ of the leftmost element of $$bits$$ such that

$$\sum_{j = i}^{i + \textrm{length of bits}}{bits[j - i] * arr[j]}$$

is a maximum. Essentially I am maximizing the element-wise multiplication between the two sequences starting at index $$i$$.

I need to solve it in $$O(n\log n)$$ or better, but I can only think of a way to do it in $$O(n^2)$$. I have a feeling prefix sums could be used but am not sure how.

• You can use FFT to compute all sums in $O(n\log n)$. Commented Jun 21, 2020 at 10:10
• Could you ellaborate? @YuvalFilmus Commented Jun 21, 2020 at 14:32
• Try working it out on your own. Commented Jun 21, 2020 at 14:58

Let the array consist of the numbers $$a_0,\ldots,a_{n-1}$$, and let the mask be $$b_0,\ldots,b_{k-1}$$. Define $$A = \sum_i a_i x^i, \quad B = \sum_j b_j x^{k-1-j}.$$ Notice that $$AB = \sum_{i,j} a_i b_j x^{i+k-1-j},$$ and so the coefficient of $$x^{i+k-1}$$ in $$AB$$ is $$\sum_{j=i}^{i+k-1} a_j b_{j-i}.$$ Therefore if you can calculate $$AB$$, you can solve your problem.
You can calculate $$AB$$ in $$O(n\log n)$$ using FFT.
• You are required to find the index $i$ at which the sum reaches its maximum. The index can be recovered from the coefficients of $AB$ in linear time. Commented Jun 22, 2020 at 9:36
• I've tried to understand FFT but I can't. Why do we even use polynomials here? Could you show me an example of FFT with two example sequences $A$ and $B$? @YuvalFilmus Commented Jun 23, 2020 at 14:36