# Rotate Function

Dec 08, 2019

$$F(k) = 0 * B_k[0] + 1 * B_k[1] + … + (n - 1) * B_k[n-1]$$

\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}

\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}

\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}

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;
}

LeetCodeLeetCode

Minimum ASCII Delete Sum for Two Strings

Longest Word in Dictionary through Deleting