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.