Problem Overview

You are given an array nums.

For every clockwise rotation of the array, we define a function:

F(k)=\sum_{i=0}^{n-1} i \cdot arr_k[i]

Where:

• arrₖ is the array after rotating k times

• Each element is multiplied by its index

Your task is to return the maximum value among all rotation functions.

This problem is popular in interviews because it tests:

• Mathematical observation

• Optimization

• Dynamic transition thinking

• Avoiding repeated computation

Example

Input:

nums = [4,3,2,6]

Rotation 0

[4,3,2,6]

F(0)=0\cdot4+1\cdot3+2\cdot2+3\cdot6=25

Rotation 1

[6,4,3,2]

F(1)=0\cdot6+1\cdot4+2\cdot3+3\cdot2=16

Rotation 2

[2,6,4,3]

F(2)=0\cdot2+1\cdot6+2\cdot4+3\cdot3=23

Rotation 3

[3,2,6,4]

F(3)=0\cdot3+1\cdot2+2\cdot6+3\cdot4=26

Maximum value:

26

Approach 1: Simulate Every Rotation

Idea

For every rotation:

• Rotate the array

• Recalculate the entire function again

Disadvantages

For each rotation:

• Rotation costs O(n)

• Computing the function costs O(n)

Total complexity becomes:

O(n^2)

With:

n <= 100000

This approach is far too slow.

Best Approach: Mathematical Transition Formula

Core Observation

Instead of recomputing every rotation from scratch, we derive a relation between:

F(k)

and

F(k-1)

This is the key optimization.

Understanding the Transition

Suppose:

nums = [4,3,2,6]

We already know:

F(0) = 25

After one clockwise rotation:

[6,4,3,2]

Notice what happens:

• Every element’s index increases by 1

• Except the last element, which moves to index 0

That creates a beautiful recurrence relation.

Transition Formula

The optimized relation becomes:

F(k)=F(k-1)+sum-n\cdot nums[n-k]

Where:

• sum = total sum of array

• nums[n-k] = element moved from end to front

• n = array size

Why This Formula Works

When rotating:

Most elements

Their indices increase by 1.

So we add:

sum

because every element contributes one extra copy of itself.

One special element

The last element jumps from index n-1 to index 0.

So we must subtract:

n\cdot nums[n-k]

to remove its previous large contribution.

This transforms the computation from:

O(n²)

into:

O(n)

Step-by-Step Example

Input

nums = [4,3,2,6]

Step 1: Compute Sum

sum = 4 + 3 + 2 + 6 = 15

Step 2: Compute F(0)

F(0)=0\cdot4+1\cdot3+2\cdot2+3\cdot6=25

Initialize:

res = 25

Step 3: Compute F(1)

Using the formula:

F(1)=F(0)+sum-n\cdot nums[3]

Substitute values:

F = 25 + 15 - 4*6

F = 16

Step 4: Compute F(2)

F(2)=F(1)+sum-n\cdot nums[2]

F = 16 + 15 - 4*2

F = 23

Step 5: Compute F(3)

F(3)=F(2)+sum-n\cdot nums[1]

F = 23 + 15 - 4*3

F = 26

Maximum becomes:

26

Why This Works

The major insight is:

Instead of recalculating all weighted sums again and again, we reuse the previous result mathematically.

This converts repeated work into a simple update formula.

That’s the entire optimization.

Time and Space Complexity

Time Complexity

O(n)

We traverse the array only twice.

Space Complexity

O(1)

No extra data structures are used.

Final Code (Optimized)

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n = nums.size();
        long long sum = 0, F = 0, res;

        for (int i = 0; i < n; i++) {
            sum += nums[i];
            F += (long long)i * nums[i];
        }

        res = F;

        for (int k = 1; k < n; k++) {
            F = F + sum - (long long)n * nums[n - k];
            res = max(res, F);
        }

        return (int)res;
    }
};

Key Interview Insight 💡

The hardest part of this problem is discovering the recurrence relation:

F(k)=F(k-1)+sum-n\cdot nums[n-k]

Once you derive this formula:

• Every rotation becomes O(1)

• Total complexity becomes linear

• No actual rotation is needed

This is a classic example of turning a brute-force problem into a mathematical optimization.