n00bie's blog

Maximum subarray sum problem for every size
By n00bie, history, 6 years ago, In English

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)

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

This problem is pretty the same as MAX-convolution, and there is no known solutions for this problem...:(

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply