Best Rotation Score
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
nums lists the values on a circular display from slot 0. The display's score is , where v_i is
the value in slot i. One turn moves every item one slot to the right (the last item goes to slot 0). You may turn the
display any number of times (including zero). Return the maximum possible score.
Examples
| nums | result |
|---|---|
[4, 3, 2, 6] | 26 |
[100] | 0 |
[-1, -2, 3] | 4 |
Example 1 — the scores after 0, 1, 2, 3 turns are 25, 16, 23 and 26.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(nums: int[]) → long
Constraints
-
nums.length -
nums[i] - The answer may not fit in 32 bits; use a 64-bit integer (
long).
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| nums | Expected |
|---|---|
[4,3,2,6] | 26 |
[100] | 0 |
[-1,-2,3] | 4 |
Hint
Hint
Let be the total and the score after k turns. One more turn adds (every item moves one slot right) and removes
for the item x = nums[n - 1 - k] that wraps from the last slot to slot 0: .
Recomputing every rotation from scratch is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1204 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 3 | verdict only |