题目来源
给定一个数组，元素个数为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;
}
};
