mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
51 lines
1.5 KiB
Markdown
51 lines
1.5 KiB
Markdown
# [396. Rotate Function](https://leetcode.com/problems/rotate-function/)
|
||
|
||
# 思路
|
||
|
||
给定一个数组，然后给出F(i)的定义，求F(i)的最大值。
|
||
此题最重要的就是根据定义快速求解出F(i)。
|
||
|
||
先写出前几项（注意将A[i]对齐了）：
|
||
```
|
||
F(0) = 0*A[0] + 1*A[1] + 2*A[2] + 3*A[3] + ... + (n-2)*A[n-2] + (n-1) * A[n-1]
|
||
F(1) = 1*A[0] + 2*A[2] + 3*A[3] + ... + (n-1)*A[n-2] + 0*A[n-1]
|
||
F(2) = 2*A[0] + 3*A[2] + 4*A[3] + ... + 0*A[n-2] + 1*A[n-1]
|
||
...
|
||
```
|
||
|
||
所以我们有
|
||
```
|
||
F(1) = F(0) + sum - A[n-1] - (n-1)*A[n-1];
|
||
F(2) = F(1) + sum - A[n-2] - (n-1)*A[n-2];
|
||
...
|
||
|
||
F(i) = F(i-1) + sum - A[n-i] - (n-1)*A[n-i] = F(i-1) + sum - n * A[n-i];
|
||
其中 sum = A[0] + A[1] + ... A[n-1]
|
||
```
|
||
|
||
所以我们可以先遍历一遍数组把sum和F(0)求出来, 再遍历一遍数组把每个F(i)都求出来同时保持一个全局最大值。
|
||
|
||
注意可能会溢出，所以我们用long long型。
|
||
|
||
两次遍历，时间复杂度O(n)，用滚动数组的思想可优化空间复杂度O(1)
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int maxRotateFunction(vector<int>& A) {
|
||
long long sum = 0, f0 = 0, n = A.size();
|
||
for(int i = 0; i < n; i++){
|
||
sum += A[i];
|
||
f0 += i*A[i];
|
||
}
|
||
long long res = f0, fi = f0;
|
||
for(int i = 1; i < n; i++){
|
||
// fi = fi + sum - A[n-i] - (n-1)*A[n-i];
|
||
fi += (sum - n * A[n-i]);
|
||
res = max(res, fi);
|
||
}
|
||
return int(res);
|
||
}
|
||
};
|
||
``` |