Stickers for Test Scores

Hard

Pupils stand in a single line, and each has a test score scores[i]. The teacher hands out stickers following two rules: - every pupil gets at least one sticker; - a pupil whose score is higher than a neighbour's in the line must get more stickers than that neighbour. Return the smallest total number of stickers that satisfies both rules.

Example 1

scores=[3, 5, 5, 1] → 6

Hand out 1, 2, 2, 1: the two middle pupils outscore their lower neighbours, and since they tie with each other there is no rule between them. 6 in total.

Example 2

scores=[9, 7, 4] → 6

Scores go down, so stickers must go down too: 3, 2, 1, which is 6.

Example 3

scores=[2] → 1

Constraints

1 ≤ len(scores) ≤ 2·10⁴
0 ≤ scores[i] ≤ 2·10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array

Similar problems

Largest Number From Two Rows Hard How Many Coins to Add Hard The Heaviest Reading Day Hard Growing Capital Project by Project Hard Levelling the Shelf Row Hard

Input

scores=[3, 5, 5, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 115 tests on the server, hidden ones included.