A monitoring agent records a server's CPU load once every second as a sequence of positive integers. Analysts call a contiguous run of consecutive seconds a surge if every reading in it is strictly greater than the reading immediately before it -- a run made of just one second always counts as a valid surge on its own. For a given trace, report the largest possible sum of readings within a single contiguous surge.
n.n integers a_1 ... a_n, the load trace.A single integer: the maximum sum of any contiguous, strictly increasing run within the trace.
Example 1
Input
5 10 20 30 5 40
Expected
60
Explanation
The run 10, 20, 30 is strictly increasing and sums to 60. The run 5, 40 sums to only 45, and the lone reading 40 sums to 40. The best surge is 10 + 20 + 30 = 60.
Example 2
Input
6 4 3 2 1 7 8
Expected
16
Explanation
Each of 4, 3, 2, 1 is followed by a smaller reading, so none of them can extend a run past one second. Starting at 1, the readings 1, 7, 8 are strictly increasing and form a surge summing to 1 + 7 + 8 = 16, the best possible.
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 →