237. Rotate Function

Just evaluate F(k) = sum(i * arr_k[i]) for each rotation and keep the maximum. With n up to 10^5 this is too slow, but it's the obvious starting point.

Approach

For each k from 0 to n - 1, compute F(k) as the dot product of indices and the array rotated k positions clockwise.

Complexity

• Time: O(n²) — n rotations, each requiring an O(n) pass.
• Space: O(1).

import java.util.*;

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int best = Integer.MIN_VALUE;
        for (int k = 0; k < n; k++) {
            int total = 0;
            for (int i = 0; i < n; i++) {
                total += i * nums[((i - k) % n + n) % n];
            }
            best = Math.max(best, total);
        }
        return best;
    }
}

Don't recompute F(k) from scratch. Look at how it changes when we rotate one more step — every element's coefficient goes up by 1, except the one element that wraps around to position 0, which loses n - 1 from its coefficient. That single insight collapses an O(n²) brute force into an O(n) sweep.

Setting up the recurrence

Let's derive the relationship between F(k - 1) and F(k) carefully. Take nums = [4, 3, 2, 6].

F(0) = 0·4 + 1·3 + 2·2 + 3·6 = 0 + 3 + 4 + 18 = 25
F(1) = 0·6 + 1·4 + 2·3 + 3·2 = 0 + 4 + 6 + 6  = 16
F(2) = 0·2 + 1·6 + 2·4 + 3·3 = 0 + 6 + 8 + 9  = 23
F(3) = 0·3 + 1·2 + 2·6 + 3·4 = 0 + 2 + 12 + 12 = 26  ← max

Compare F(0) and F(1) term-by-term. Going from rotation 0 to rotation 1, each element's index (its coefficient) shifts by +1:

• 4 was at index 0, now at index 1 — coefficient up by 1.
• 3 was at index 1, now at index 2 — up by 1.
• 2 was at index 2, now at index 3 — up by 1.
• 6 was at index 3, but it can't go to index 4 — it wraps around to index 0.

So three elements gained +1 to their coefficient (contributing + (4 + 3 + 2) to the total) and one element dropped from coefficient 3 to 0 (contributing - 3·6). That gives:

F(1) - F(0) = (4 + 3 + 2) - 3·6 = 9 - 18 = -9
F(1) = F(0) - 9 = 25 - 9 = 16  ✓

Cleaning the formula

Notice that (4 + 3 + 2) is just sum(nums) - 6, i.e. S - nums[n - 1]. Substituting:

F(1) - F(0) = (S - nums[n - 1]) - (n - 1) · nums[n - 1]
            = S - n · nums[n - 1]

Generalising, the element that wraps to index 0 when going from F(k - 1) to F(k) is nums[n - k]. So:

F(k) = F(k - 1) + S - n · nums[n - k]

Steps

1. Compute S = sum(nums) and F = sum(i · nums[i]) (this is F(0)).
2. Track best = F.
3. For k = 1, 2, …, n - 1:
   • Update F += S - n · nums[n - k].
   • Update best = max(best, F).
4. Return best.

Walk-through

nums = [4, 3, 2, 6], n = 4, S = 15.

Answer: 26.

Edge cases

• Single element: the loop never runs; F(0) = 0. Correct.
• All zeros: every F(k) equals 0.
• Negative values: the recurrence still holds — no special-case needed.

Complexity

• Time: O(n) — one pass for S and F(0), one pass for the recurrence.
• Space: O(1).