Show problems as
Classic problem #396MediumArrayMathDynamic Programming

Rotate Function

Real-world version: Best Dial Offset Score
Tracked in this browser only
Read Rotate Function on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A calibration dial has n slots arranged in a circle, and slot i holds the signed reading nums[i]. A read head lines up with one slot and then walks all the way round, giving heavier credit to later stops.

Starting the head at slot k, the sequence it visits is B with B[i] = nums[(i + k) % n] for i from 0 to n - 1, and the score of that start is

score(k) = 0 * B[0] + 1 * B[1] + 2 * B[2] + ... + (n - 1) * B[n - 1]

Return the largest score(k) over the n possible starting slots 0 <= k < n. Readings may be negative, so the best start is not always slot 0.

Examples

Example 1

Input
nums = [4, -1, 6, 2]
Output
22

Starting at slot 1 the head reads [-1, 6, 2, 4] and scores 0*(-1) + 1*6 + 2*2 + 3*4 = 22, which is the reported value.

Example 2

Input
nums = [7]
Output
0

A one-slot dial has a single start and the only weight is 0, so the score is 0.

Example 3

Input
nums = [-3, -8, -2]
Output
-8

Every start scores below zero. Starting at slot 1 the head reads [-8, -2, -3] for 0*(-8) + 1*(-2) + 2*(-3) = -8, the value returned.

Example 4

Input
nums = [0, 5, -5, 9, 1]
Output
31

Starting at slot 2 the head reads [-5, 9, 1, 0, 5] and scores 0*(-5) + 1*9 + 2*1 + 3*0 + 4*5 = 31, the value returned.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • -100 <= nums[i] <= 100

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.

Python
def best_dial_score(readings: list[int]) -> int:
Java
public int bestDialScore(int[] readings)

More on the same topics