Rotate Function

medium array math dp

Problem

Define F(k) = 0·B_k[0] + 1·B_k[1] + … + (n−1)·B_k[n−1] where B_k is nums rotated k positions clockwise. Return the maximum F(k) over k = 0, 1, …, n−1.

Inputnums = [4, 3, 2, 6]

Output26

F(3) = 0·6 + 1·4 + 2·3 + 3·2 = … key recurrence: F(k) = F(k−1) + sum − n·nums[n−k].

nums (comma-separated)

def max_rotate_function(nums):
    n, total = len(nums), sum(nums)
    f = sum(i * v for i, v in enumerate(nums))
    best = f
    for k in range(1, n):
        f = f + total - n * nums[n - k]
        best = max(best, f)
    return best

function maxRotateFunction(nums) {
  const n = nums.length;
  const total = nums.reduce((a, b) => a + b, 0);
  let f = 0;
  for (let i = 0; i < n; i++) f += i * nums[i];
  let best = f;
  for (let k = 1; k < n; k++) {
    f = f + total - n * nums[n - k];
    best = Math.max(best, f);
  }
  return best;
}

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

int maxRotateFunction(vector<int>& nums) {
    int n = nums.size(), total = 0, f = 0;
    for (int i = 0; i < n; i++) { total += nums[i]; f += i * nums[i]; }
    int best = f;
    for (int k = 1; k < n; k++) {
        f = f + total - n * nums[n - k];
        best = max(best, f);
    }
    return best;
}

Explanation

Computing F(k) from scratch for every rotation would be slow. The trick is a recurrence that turns each new rotation into a cheap one-line update from the previous one.

When you rotate the array by one more step, every element's weight goes up by 1 (adding sum(nums) to the score), except the element that wraps from the back to the front, which drops from weight n-1 to weight 0. That gives F(k) = F(k-1) + total - n * nums[n - k].

So we compute F(0) directly as Σ i·nums[i], then slide through k = 1 .. n-1 updating f with that formula and keeping the running best.

Example: nums = [4, 3, 2, 6], total = 15. F(0) = 0·4 + 1·3 + 2·2 + 3·6 = 25. Then F(1) = 25 + 15 - 4·nums[3] = 25 + 15 - 24 = 16, and continuing this way the maximum found is 26.

Because each step is O(1), the whole scan is linear instead of quadratic.

Time: O(n) Space: O(1)