Description
You are given an integer array nums of length n.
Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].
Return the maximum value of F(0), F(1), ..., F(n-1).
The test cases are generated so that the answer fits in a 32-bit integer.
Examples:
Example 1:
Input: nums = [4,3,2,6]
Output: 26
Explanation:
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
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
Example 2:
Input: nums = [100]
Output: 0Solution in Python
To solve this problem, let’s break down how we can efficiently compute the rotation function F(k) for different values of k without recalculating everything from scratch.
Analysis and Approach
Given:
- nums is the original array.
- F(k)=0×arrk[0]+1×arrk[1]+…+(n−1)×arrk[n−1]
- arr_k is the array obtained by rotating nums by k positions clockwise.
Insights
- Deriving F(k) from F(k−1):
- Let’s calculate F(0) directly: F(0)=0×nums[0]+1×nums[1]+2×nums[2]+…+(n−1)×nums[n−1]
- If we rotate nums by 1 position (clockwise):
- The last element moves to the front.
- Every other element shifts one position to the right.
- Let’s derive a relationship: F(k)=F(k−1)+sum(nums)−n×nums[n−k]
- sum(nums) is the sum of all elements in the array.
- nums[n-k] is the element that moved from the last position to the front in the current rotation.
- Optimized Approach:
- Calculate F(0) and sum(nums).
- Use the derived formula to compute F(k) for all k from 1 to n−1 in O(n) time.
Python
class Solution:
def maxRotateFunction(self, nums: List[int]) -> int:
n = len(nums)
# Calculate the sum of all elements in nums
total_sum = sum(nums)
# Calculate F(0)
F_0 = sum(i * nums[i] for i in range(n))
# Initialize max_value with F(0)
max_value = F_0
current_F = F_0
# Calculate F(k) for k from 1 to n-1 using the derived formula
for k in range(1, n):
# F(k) = F(k-1) + total_sum - n * nums[n-k]
current_F = current_F + total_sum - n * nums[n - k]
# Update max_value if the current F(k) is greater
max_value = max(max_value, current_F)
return max_valueExplanation of the Code
- Initialization:
total_sumstores the sum of all elements in the array.F_0computes the rotation function for F(0) using a list comprehension.
- Iterative Calculation:
- We initialize
max_valuewith F(0). - For each k from 1 to n−1:
- Use the formula to compute F(k) from F(k−1).
- Update
max_valueif F(k) is greater than the current maximum.
- We initialize
- Return:
- The maximum value found across all rotations.
Solution in C++
C++
class Solution {
public:
int maxRotateFunction(vector<int>& nums) {
int n = nums.size();
long long sum_nums = 0; // Sum of all elements in nums
long long F_0 = 0; // F(0)
// Calculate sum_nums and F(0)
for (int i = 0; i < n; i++) {
sum_nums += nums[i];
F_0 += i * nums[i];
}
long long max_value = F_0; // Initialize max_value with F(0)
long long current_F = F_0; // Current value of F(k)
// Calculate F(k) for k = 1 to n-1 using the relationship
for (int k = 1; k < n; k++) {
// F(k) = F(k-1) + sum_nums - n * nums[n-k]
current_F = current_F + sum_nums - n * nums[n - k];
// Update the maximum value found
max_value = max(max_value, current_F);
}
// Return the maximum value of F(k)
return static_cast<int>(max_value);
}
};Solution in Javascript
JavaScript
var maxRotateFunction = function(nums) {
const n = nums.length;
// Step 1: Calculate sum of all elements in nums
let totalSum = 0;
for (let num of nums) {
totalSum += num;
}
// Step 2: Calculate F(0)
let F0 = 0;
for (let i = 0; i < n; i++) {
F0 += i * nums[i];
}
// Initialize max value as F(0)
let maxVal = F0;
// Step 3: Calculate F(k) using the relationship F(k) = F(k-1) + sum(nums) - n * nums[n-k]
let currentF = F0;
for (let k = 1; k < n; k++) {
currentF = currentF + totalSum - n * nums[n - k];
// Update maxVal if currentF is greater
maxVal = Math.max(maxVal, currentF);
}
// Step 4: Return the maximum value found
return maxVal;
};Solution in Java
Java
class Solution {
public int maxRotateFunction(int[] nums) {
int n = nums.length;
int sum = 0;
int F = 0;
// Calculate sum of all elements in nums and F(0)
for (int i = 0; i < n; i++) {
sum += nums[i];
F += i * nums[i];
}
// Initialize the maximum value with F(0)
int maxF = F;
// Calculate F(k) for k = 1 to n-1 using the relation:
// F(k) = F(k-1) + sum - n * nums[n-k]
for (int k = 1; k < n; k++) {
F = F + sum - n * nums[n - k];
maxF = Math.max(maxF, F);
}
return maxF;
}
}