values. The spread of a segment is the difference between its largest and smallest elements; a segment is a non-empty run of consecutive elements.
Return the sum of the spreads of all segments of the array.
An O(n²) scan fits the limits; as a bonus, try to find an O(n) solution.values=[4, 1, 3] → 8
Spreads: [4, 1] gives 3, [1, 3] gives 2, [4, 1, 3] gives 3, and single elements give 0. Total 8.
values=[-2, -2, 5] → 14
[-2, -2] gives 0, [-2, 5] gives 7, [-2, -2, 5] gives 7. Total 14.
values=[6] → 0
The only segment has one element, so its spread is 0.
values=[4, 1, 3]
8
Run checks the first 3 tests in your browser. Submit checks all 130 tests on the server, hidden ones included.