Rotate Function

What the problem is really asking

For every clockwise rotation of nums, compute the weighted sum:

F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]

Then return the largest value among all rotations.

The trap is that building every rotated array would be too slow for n <= 100000. We need to reuse the previous rotation's answer.

Key observation

Let:

• total be the sum of all numbers in nums
• current be the value of the current rotation function

Start with:

F(0) = 0 * nums[0] + 1 * nums[1] + ... + (n - 1) * nums[n - 1]

When we rotate once clockwise, every element's index increases by 1, except the last element, which moves to index 0.

So compared with F(0):

• every element contributes +nums[i]
• but the old last element was counted one extra time too many, so subtract n * nums[n - 1]

That gives:

F(1) = F(0) + total - n * nums[n - 1]

More generally:

F(k) = F(k - 1) + total - n * nums[n - k]

This recurrence is the whole problem.

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int total = 0;
        int current = 0;

        for (int i = 0; i < n; i++) {
            total += nums[i];
            current += i * nums[i];
        }

        int answer = current;

        for (int i = n - 1; i > 0; i--) {
            current += total - n * nums[i];
            answer = Math.max(answer, current);
        }

        return answer;
    }
}

Dry run

Take nums = [4, 3, 2, 6].

First calculate:

• total = 15
• F(0) = 0 * 4 + 1 * 3 + 2 * 2 + 3 * 6 = 25

Now use the recurrence:

• F(1) = 25 + 15 - 4 * 6 = 16
• F(2) = 16 + 15 - 4 * 2 = 23
• F(3) = 23 + 15 - 4 * 3 = 26

The maximum value is 26.

Why the recurrence works

Imagine shifting from one rotation to the next.

Most numbers move one index to the right, so their multiplier increases by 1. Adding all numbers once accounts for that index increase.

But the element that wraps from the end to the front should no longer have multiplier n - 1; it should become multiplier 0. Since adding total also added this wrapping element once, we remove its full n copies with n * nums[i].

That is why each update is:

current = current + total - n * wrappingElement

Common mistakes

1. Actually rotating the array

Rotating for every k and recomputing the score takes too much time. The recurrence gives each next value in O(1).

2. Using the wrong wrapping index

For clockwise rotations, the elements wrap from the end of the original array in this order:

nums[n - 1], nums[n - 2], nums[n - 3], ...

That is why the loop walks backward from n - 1 to 1.

3. Forgetting the single-element case

When nums has one element, F(0) is always 0. The same initialization handles it naturally.

Complexity

Time Complexity: O(n)

We compute the sum and F(0) once, then update the rotation function n - 1 times.

Space Complexity: O(1)

Only a few variables are needed.