Rotate Function
source link: http://blog.codeand.fun/2019/12/08/Rotate-Function/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
第32天。
今天的题目是 Rotate Function 。
这道题是一道数学题，直接求解的话显然复杂度很高，然后这道题也没法把大问题化简到小问题，所以用常规的分治、动规和贪心去想这道题的话，是没法找到答案的。
为了解决这道题，我们先把 $F(k)$ 的写出来：
$$
F(k) = 0 * B_k[0] + 1 * B_k[1] + … + (n - 1) * B_k[n-1]
$$
然后我们通过题意可以知道 $B_k[i] = A[(i+k) % n]$ ，所以：
$$
\begin{aligned}
F(k) &= 0 * B_k[0] + 1 * B_k[1] + … + (n - 1) * B_k[n-1] \
&= 0 * A[(0+k) % n] + A[(1+k) % n] + … + (n - 1) * A[(n-1+k) % n] \
&= \sum_{i=0}^{n-1} i * A[(i+k) % n]
\end{aligned}
$$
我们可以尝试把 $(i + k) % n$ 中的 取模运算去掉：
$$
\begin{aligned}
F(k) &= \sum_{i=0}^{n-1} i * A[(i+k) % n] \
&= \sum_{i=1}^{n-k-1} i * A[i+k] + \sum_{i=n-k}^{n-1} i * A[i + k -n] \
\end{aligned}
$$
我们把 $j = i - k$ 代入 $\sum_{i=1}^{n-k-1} i * A[i+k]$ 和 $j = i + k -n$ 代入 $\sum_{i=n-k}^{n-1} i * A[i + k -n]$ :
$$
\begin{aligned}
F(k) &= \sum_{j=k}^{n-1} (j - k) * A[j] + \sum_{j=0}^{k-1} (j + n -k) * A[j] \
& = \sum_{j=0}^{n-1} j * A[j] + n * \sum_{j=0}^{k-1} A[j] - k * \sum_{j=0}^{n-1} A[j]
\end{aligned}
$$
上面的公式中 $\sum_{j=0}^{n-1} j * A[j]$ 和 $\sum_{j=0}^{n-1} A[j]$ 都是常数，因此我们可以可以用 $O(n)$ 的时间复杂度解决这道题：
int maxRotateFunction(vector<int>& A) {
if (A.size() == 0) return 0;
long long s1 = 0, s2 = 0;
for(int i = 0, size = A.size(); i < size; i++) {
s1 += A[i];
s2 += i*A[i];
}
long long res = LONG_MIN;
long long t = 0;
for(int k = 0, n = A.size();k < n; k++) {
t += A[k];
res = max(res,n * t - (k+1) * s1);
}
return res + s2;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK