Dare2Solve
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
.
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.
F(0)
and the sum of all elements in nums
.F(k)
for k = 1, 2, ..., n-1
based on the previous value of F(k-1)
.F(k) = F(k-1) + sum(nums) - n * nums[n - k]
.F(k)
during the iterations.O(n)
, where n
is the length of nums
.
O(1)
, as we only use a few variables to store intermediate values.
class Solution {
public:
int maxRotateFunction(vector<int>& 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;
}
};
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
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;
}
}
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;
}