A harbour tide gauge logs rise[k], the change in water level during hour k (negative when the
water falls). A technician admits that the sensor may have been wired backwards for one
contiguous stretch of hours, so the readings in that stretch may have the wrong sign. Nobody
knows which stretch, or whether it happened at all.
For the harbour master's best-case report, you may choose at most one contiguous stretch of hours and flip the sign of every reading in it. Then pick a non-empty run of consecutive hours. Return the largest possible total of the readings in that run.
Examples
Input: rise = [3, -4, 5, -2, -6, 4]
Output: 17
Explanation: Flip the stretch [-2, -6] and take the run 5, 2, 6, 4.
Input: rise = [-3, -1, -2]
Output: 6
Explanation: Flip every hour and take all of them.
Input: rise = [2, 1]
Output: 3
Explanation: Flipping nothing is allowed.
Constraints
1 <= len(rise) <= 10**5,-10**4 <= rise[k] <= 10**4- Target complexity: O(n) time. Trying every run, even with a clever inner loop, is too slow for the largest tests.
Goals
- Split a Kadane scan into several states for before, inside and after a special block
- See that flipping a block only matters where it overlaps the chosen run
- Keep every state a non-empty run so the answer never becomes an empty stretch