Rotate Function

题目来源
给定一个数组，元素个数为n，旋转n-1次，然后每次计算各个元素和自身索引乘积和，求最大值。
我想着把所有情况都算一遍，代码如下：

class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        int n = A.size();
        if (n == 0)
            return 0;
        long long maxVal = INT_MIN;
        for (int i=0; i<n; i++) {
            long long curVal = 0;
            for (int j=0; j<n; j++) {
                curVal += A[j] * ((i + j) % n);
            }
            maxVal = max(maxVal, curVal);
        }
        return maxVal;
    }
};

然后又不出意料的超时了。
这是一道数学题，递推公式F(k) = F(k-1) + sum - nBk[0]。
现在数学真是渣成狗了。

class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        int n = A.size();
        if (n == 0)
            return 0;
        long long F = 0;
        long long allSum = 0;
        for (int i=0; i<n; i++) {
            F += i * A[i];
            allSum += A[i];
        }
        long long maxVal = F;
        for (int i=n-1; i>=1; i--) {
            F = F + allSum - n * A[i];
            maxVal = max(F, maxVal);
        }
        return maxVal;
    }
};