LC 396 Rotate Function(M)

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:

F(k) = 0 Bk[0] + 1 Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

public int maxRotateFunction(int[] A)

解题思路 DP

如果暴力解题，时间复杂度是O(n2), 分析 f(0)和f(1)的区别， 假设现在方程值是f，A的所有值的和是sum 那么一次向右循环位移可以认为 1、首先所有值都加一个自身，也就是和加上sum 2、扣除1中多加的最后一个，以及原来就应该减掉的n个了，减掉A[n-i]*n就好

public int maxRotateFunction(int[] A) {
    int n = A.length;
    int sum = 0;
    int f = 0;
    // count f0 and sum
    for(int i = 0; i < n; i++){
        f += i *A[i];
        sum += A[i];
    }
    int max = f;
    for(int j = 1; j < n; j++){
        // 加一个sum 并 减去左移的
        f = f + sum - n*A[n-j];
        max = Math.max(max, f);
    }
    return max;
}