Sum of Subarray Ranges
Real-world version: Total Swing Across Every StretchThe statement here is our own: the same inputs, outputs and technique.
A sailplane carries a barograph that writes down one altitude reading a minute for the whole flight. readings lists them in flight order, each in metres measured against the ridge line the pilot is working, so a reading taken below the ridge is negative.
A stretch is any run of one or more consecutive readings, identified by where it starts and where it ends. The swing of a stretch is its highest reading minus its lowest reading; a stretch holding a single reading therefore swings 0.
Return the sum of the swings of every stretch of readings. A flight of n readings has n * (n + 1) / 2 stretches, and the total can be far larger than a 32-bit integer holds, so it must be returned as a 64-bit value.
Examples
Example 1
- Input
- readings = [12, -5, 12, 30, -5]
- Output
- 279
The five single-minute stretches each swing 0. The four two-minute stretches swing 17, 17, 18 and 35, the three three-minute stretches swing 17, 35 and 35, the two four-minute stretches swing 35 and 35, and the whole flight swings 35, which adds up to the figure returned.
Example 2
- Input
- readings = [4, 4, 4, 4]
- Output
- 0
Every stretch, however long, has the same highest and lowest reading, so each one swings 0.
Example 3
- Input
- readings = [7]
- Output
- 0
A single reading forms the only stretch, and its highest and lowest reading are the same.
Example 4
- Input
- readings = [1000000000, -1000000000]
- Output
- 2000000000
There are three stretches: the two single readings swing 0 each, and the pair swings 2000000000, which is past what a 32-bit integer holds.
Constraints
- 1 <= readings.length <= 1000
- -10^9 <= readings[i] <= 10^9
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def total_swing(readings: list[int]) -> int:public long totalSwing(int[] readings)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 4 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's