Funcia
Lv.1arraydpmath

Best Rotation Score

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

nums lists the values on a circular display from slot 0. The display's score is F=∑ii⋅viF = \sum_i i \cdot v_i, 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

numsresult
[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

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • −106≤-10^6 \le nums[i] ≤106\le 10^6
  • The answer may not fit in 32 bits; use a 64-bit integer (long).

Expected complexity

Time
O(N)
Space
O(1)

Examples

numsExpected
[4,3,2,6]26
[100]0
[-1,-2,3]4

Hint

Hint

Let SS be the total and F(k)F(k) the score after k turns. One more turn adds SS (every item moves one slot right) and removes n⋅xn \cdot x for the item x = nums[n - 1 - k] that wraps from the last slot to slot 0: F(k+1)=F(k)+S−n⋅xF(k+1) = F(k) + S - n \cdot x. Recomputing every rotation from scratch is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251204 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.