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)
This problem is pretty the same as MAX-convolution, and there is no known solutions for this problem...:(
That's too bad :( Thanks a lot though, I was feeling stupid since it didn't look like a very tough problem at first glance