396. Rotate Function

Description

The problem requires calculating the maximum value of the rotation function F(k) for a list of integers nums, where F(k) is defined as F(k) = 0 * nums[k % n] + 1 * nums[(k+1) % n] + ... + (n-1) * nums[(k + n-1) % n]. We are tasked with finding the maximum value of F(k) over all possible k.

Intuition

The rotation function F(k) can be optimized by recognizing a recursive relationship. Instead of recalculating F(k) from scratch for each rotation, we observe that F(k) can be derived from F(k-1) using a formula based on the sum of all elements in nums and the previously computed result.

Approach

1. Calculate the initial value F(0) and the sum of all elements in nums.
2. Use a loop to compute F(k) for k = 1, 2, ..., n-1 based on the previous value of F(k-1).
3. The transition formula is F(k) = F(k-1) + sum(nums) - n * nums[n - k].
4. Track the maximum value of F(k) during the iterations.

Complexity

Time Complexity:

O(n), where n is the length of nums.

Space Complexity:

O(1), as we only use a few variables to store intermediate values.

Code

C++

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

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

        long long maxF = F;

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

        return maxF;
    }
};

Python

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        F = sum(i * nums[i] for i in range(n))
        total_sum = sum(nums)

        maxF = F

        for k in range(1, n):
            F = F + total_sum - n * nums[n - k]
            maxF = max(maxF, F)

        return maxF

Java

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        long F = 0, sum = 0;

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

        long maxF = F;

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

        return (int) maxF;
    }
}

JavaScript

function maxRotateFunction(nums) {
    const n = nums.length;
    let F = 0;
    let sum = 0;
    F = nums.map((elem, index) => elem * index).reduce((a, b) => a + b, 0)
    sum = nums.reduce((a, b) => a + b, 0)

    let maxF = F;

    for (let k = 1; k < n; k++) {
        F = F + sum - n * nums[n - k];
        maxF = Math.max(maxF, F);
    }

    return maxF;
}