A fiber backbone runs through n relay stations in a straight line, numbered 1 to n. Station i reports a net signal value g_i — a gain, or a loss (negative) if attenuation outweighs amplification at that station. For any station i, define its left reach as the sum of signal values from station 1 through station i inclusive, and its right reach as the sum of signal values from station i through station n inclusive; station i itself is counted in both sums. Station i's peak score is the larger of its left reach and its right reach. Find the maximum peak score achievable over every choice of station.
n, the number of relay stations.n space-separated integers g_1 ... g_n.Print a single integer: the maximum peak score over all stations i (1 <= i <= n).
Example 1
Input
4 4 3 -2 8
Expected
13
Explanation
Left reaches are 4, 7, 5, 13 and right reaches are 13, 9, 6, 8 (station i counted in both). Peak scores are max(4,13)=13, max(7,9)=9, max(5,6)=6, max(13,8)=13. The maximum over all stations is 13.
Example 2
Input
3 -5 -1 -3
Expected
-3
Explanation
Left reaches are -5, -6, -9 and right reaches are -9, -4, -3. Peak scores are max(-5,-9)=-5, max(-6,-4)=-4, max(-9,-3)=-3. The best achievable peak score is -3, coming from station 3 alone; the full-array total (-9) is worse, showing the global sum isn't always the answer when values are negative.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →