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