题目描述：

给定一个长度为 n 的整数数组 nums 。

假设 arr_k 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数 F 为：

F(k) = 0 * arrk[0] + 1 * arrk[1] + … + (n - 1) * arrk[n - 1]
返回 F(0), F(1), …, F(n-1)中的最大值 。

生成的测试用例让答案符合 32 位 整数。

示例 1:
输入: nums = [4,3,2,6]
输出: 26
解释:
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
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。

示例 2:
输入: nums = [100]
输出: 0

提示:
n == nums.length
1 <= n <= 10⁵
-100 <= nums[i] <= 100

解题思路一：这种题一般不可暴力，需要找出F(n)与F(n-1)之间的关系，利用F(n-1)来求F(n)，用数组存储，以空间换时间。公式具体过程看注释。

class Solution {
public:
    //F(n)=F(n-1)+sum(nums)-(n)*arr[n-n]
    //F(i)=F(i-1)+sum(nums)-(n)*arr[n-i]
    //F(1)=25+15-4*6=16
    //F(2)=16+15-4*2=23
    //F(3)=23+15-4*3=26
    //F(n)用数组存，sum固定，n*arr[n-i]
    int maxRotateFunction(vector<int>& nums) {
        int n=nums.size();
        int sum=accumulate(nums.begin(),nums.end(),0);
        vector<int> F(n);
        int F0=0;
        for(int i=0;i<n;++i){
            F0+=i*nums[i];
        }
        F[0]=F0;//先算出F[0]
        for(int i=1;i<n;++i){
            F[i]=F[i-1]+sum-n*nums[n-i];
        }
        int ans=INT_MIN;
        for(int i=0;i<n;++i){
            ans=max(ans,F[i]);
        }
        return ans;
    }
};

解题思路二：我们可以不用数组存储中间值，利用ans存储我们需要的最大值即可

用F[0]求之后的值

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n=nums.size();
        int sum=accumulate(nums.begin(),nums.end(),0);
        int F0=0;
        for(int i=0;i<n;++i){//先算出F[0]
            F0+=i*nums[i];
        }
        int ans=F0;
        for(int i=n-1;i>=1;--i){
            //F[i]=F[i-1]+sum-n*nums[n-i];
            F0+=sum-n*nums[i];
            ans=max(F0,ans);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。计算 numSum 和第一个 f 消耗 O(n) 时间，后续迭代 n−1 次 f消耗 O(n) 时间。

空间复杂度：O(1)。仅使用常数空间。