Problem 280031 · medium · Level 02 Linear Data Structures

Steepest Climb

arrays · runs · best-so-far

gains lists the positive elevation gains of consecutive trail segments. A climb is a contiguous block of segments whose gains are strictly increasing. The steepness of a climb is the sum of its gains. Return the largest steepness of any climb in the list.

Examples

Input:  gains = [10, 20, 30, 5, 10, 50]
Output: 65
Explanation: 5, 10, 50 is a climb worth 65, more than 10, 20, 30 (60).

Input:  gains = [12, 17, 15, 13, 10, 11, 12]
Output: 33
Explanation: 10, 11, 12 sums to 33.

Constraints

  • 1 <= len(gains) <= 10**5
  • 1 <= gains[i] <= 100
  • Target: O(n) time, O(1) extra space.

Goals

  • Accumulate a sum over a strictly increasing run
  • Restart the accumulation when the run breaks
Starting Python…