Блог пользователя ManFails

Автор ManFails, история, 13 месяцев назад, По-английски

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)$$$?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
13 месяцев назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

.

  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    funny how you just reached cyan and talking shit

»
13 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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