Rotate Function
Medium · 1-D Dynamic Programming · Explanation and code example
Rotate-Sum Recurrence
How it works
When the last value moves to index zero, every other value’s weight increases by one. The new weighted sum equals the old weighted sum plus the total array sum minus n times the moved value. Reuse this recurrence instead of recomputing each rotation.
Steps
- Compute the initial weighted sum and total sum.
- Process moved values from the array’s right end.
- Update the weighted sum with total - n × moved and track its maximum.
Complexity
- Time: O(n).
- Space: O(1).
Things to watch for
- The subtracted term belongs to the value moving from last to first.
- Initialize from the real weighted sum so negative answers work.
- No physical array rotation is needed.
Python code example
class Solution:
def maxRotateFunction(self, nums: list[int]) -> int:
f = sum(i * num for i, num in enumerate(nums))
ans = f
summ = sum(nums)
for a in reversed(nums):
f += summ - len(nums) * a
ans = max(ans, f)
return ans
C++ code example
class Solution {
public:
int maxRotateFunction(vector<int>& nums) {
const int sum = accumulate(nums.begin(), nums.end(), 0);
int f = 0;
// Calculate F(0) first.
for (int i = 0; i < nums.size(); ++i)
f += i * nums[i];
int ans = f;
for (int i = nums.size() - 1; i > 0; --i) {
f += sum - static_cast<int>(nums.size()) * nums[i];
ans = max(ans, f);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.