Domonion's blog

Simple dp
By Domonion, history, 8 years ago, In English

You are given a sequence

Unable to parse markup [type=CF_TEX]

.

You can split this sequence into contiguous non-empty parts

Unable to parse markup [type=CF_TEX]

.

Your task is to find the maximum value

Unable to parse markup [type=CF_TEX]

. If k = 1 then sum equal to 0.

Can anyone help me come up with solution?

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

»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Let

Unable to parse markup [type=CF_TEX]

be the maximum value I can get with the first n elements of the sequence if the length of the last block is len. It is easy to see the formula

Unable to parse markup [type=CF_TEX]

where si is the accumulative sum of the first i elements. Now

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

the first part can be calculated using convex hull trick, the complexity will be
→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In your question it is not clear whether you are given k or not. If you are not given k the solution provided by jcg will be correct. If you are given k the problem can be solved using the approach described here and here in

Unable to parse markup [type=CF_TEX]

. But it can be further optimised to

Unable to parse markup [type=CF_TEX]

, because we can do convex hull (which we actually use inside the binary search) in O(1) time using a stack.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems that I reply to the correct statement.. In your version how you deal with the queries in the convex hull in O(1)? The values in the original sequence can be negative.

    → Reply