This problem was in recent codechef contest

https://www.codechef.com/COOK98B/problems/OETW

It's actually very simple, but I could not see that at first, and reduced it to the following subproblem (even the reduction might be wrong, but that doesn't matter):

Given a binary array of size n, we need the maximum subarray sum for every size k = 1..n

Can this problem be solved for n<=2e6 ? I can't think of anything better than O(n^2)