ManFails's blog

How to solve this task using DP
By ManFails, history, 13 months ago, In English

Hello Codeforces,

I was trying to solve F1. Omsk Metro (simple version) when I got stuck in the following sub-problem:

given an array $$$A$$$ of length $$$n$$$, for each $$$i$$$ from $$$1$$$ to $$$n$$$ find the maximum sum of a continuous subsegment (let's denote it $$$Ans_i$$$) from $$$A_0$$$ to $$$A_i$$$. For example: suppose $$$A = [1, -1, 1, 1, 1]$$$ then:

$$$Ans_1 = 1$$$ (continuous subsegment from $$$A_1 to A_1$$$)

$$$Ans_2 = 1$$$ (continuous subsegment from $$$A_1 to A_1$$$)

$$$Ans_3 = 1$$$ (continuous subsegment from $$$A_1 to A_1$$$ or $$$A_3 to A_3$$$ or $$$A_1 to A_3$$$)

$$$Ans_4 = 2$$$ (continuous subsegment from $$$A_1 to A_4$$$ or $$$A_3 to A_4$$$)

$$$Ans_5 = 3$$$ (continuous subsegment from $$$A_1 to A_5$$$ or $$$A_3 to A_5$$$)

Constraints:

  • $$$A_i$$$ can only be $$$1$$$ or $$$-1$$$.

  • $$$1 <= n <= 2 * 10^5$$$

Can this be solved in $$$O(n)$$$?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 months ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Dude, if you can help someone asking a question then go ahead, if not then the least you could do is not demoralize them.

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

    funny how you just reached cyan and talking shit

    → Reply
»
13 months ago, # |
  Vote: I like it +11 Vote: I do not like it

This is the maximum subarray sum problem and can be solved in $$$O(n)$$$ for any $$$A_i$$$.

→ Reply