Problem statement: Let $$$s=\sum\limits_{j=1}^{i-1} a_j$$$, and update $$$a_i$$$ to $$$a_i-s$$$, $$$a_i$$$, or $$$a_i+s$$$. Find the largest possible value of $$$\max\limits_{i=1}^n a_i$$$ at the end.
We observe that when $$$s$$$ is positive, it is obvious that we choose to set $$$a_i\gets a_i+s$$$, and when $$$s$$$ is negative, we can choose to set $$$a_i\gets a_i-s$$$ ($$$a_i\gets a_i+(-s)$$$) so that the contribution is positive. Therefore $$$a_i$$$ will ultimately be assigned the value $$$a_i+|s|$$$. To make the contribution larger, we need $$$|s|$$$ to be larger, which means we need $$$s$$$ to be very large or very small (i.e., a large absolute value). At this point we can use two variables $$$l,h$$$ (corresponding to minn and maxn in the code) to denote the smallest and largest prefix sums achievable so far, respectively. Putting this together, we update our answer as $$$\text{ans}\gets \max{\text{ans},|l|,|h|}$$$, and finally output $$$\text{ans}$$$.
So how do we maintain this maximum and minimum? Consider the current position $$$i$$$; the newly updated prefix sum $$$s'$$$ has three possibilities: $$$s\in{s+(a_i-s),s+a_i,s+(a_i+s)}$$$, i.e. $$$s\in{a_i,a_i+s,a_i+2s}$$$. Therefore we update $$$l'\gets \min{a_i,a_i+l,a_i+2l}$$$ and $$$h'\gets \max{a_i,a_i+h,a_i+2h}$$$. Since $$$l$$$, whether positive or negative, can never be smaller than $$$a_i$$$ or $$$a_i+2l$$$, and similarly for $$$h$$$, the two expressions can be rewritten as $$$l'\gets a_i+\min(0,2l)$$$ and $$$h'\gets a_i+\max(0,2h)$$$.
And with that, we are done with this problem.
Comments (0)
