Loading...
Loading...
Loading...
A tuition teacher gives sweets to n students sitting in a row, based on their test ratings. Every student gets at least one sweet. A student whose rating is higher than the student right next to them must get more sweets than that neighbour. Two neighbours with equal ratings have no rule between them.
Print the smallest total number of sweets the teacher needs.
Example 1
Input
3 1 0 2
Output
5
Give 2, 1 and 2 sweets. Both ends have a higher rating than the middle student. The total is 5.
Example 2
Input
3 1 2 2
Output
4
Give 1, 2 and 1. The last student ties with the middle one, so one sweet is enough. The total is 4.
Try the problem first. Open one hint at a time.
Each student has two rules: one with the left neighbour and one with the right neighbour. Handle them one side at a time.
Start everyone at 1. Go left to right: if a student beats the left neighbour, give one more than that neighbour.
Then go right to left: if a student beats the right neighbour, they need at least one more than that neighbour.
In the second pass take the larger of the two needs, so you do not undo the first pass. The total can pass the int range, so add it up in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor