🎨Now live: Try our Free AI Image Generation Feature

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
- Calculate the initial value
F(0)
and the sum of all elements innums
. - Use a loop to compute
F(k)
fork = 1, 2, ..., n-1
based on the previous value ofF(k-1)
. - The transition formula is
F(k) = F(k-1) + sum(nums) - n * nums[n - k]
. - 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;
}