396. Rotate Function

T: O(n)

```java
class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int sum = 0;
        int f = 0;
        for (int i = 0; i < n ; i++) {
            sum += nums[i];
            f += i*nums[i]; // f0
        }
        int result = f;
        for (int i = 1; i < n; i++) {
            f = f + sum - n*nums[n - i];
            result = Math.max(f, result);
        }
        return result;
    }
}

/**
when k = 0
f(k) =    0*nums[0] + 1*nums[1] + 2*nums[2] +. ...                  + (n-2)*nums[n-2] + (n-1)*nums[n-1]
f(k-1) =  0*nums[1] + 1*nums[2] +....                               + (n-2)*nums[n-1] + (n-1)*nums[0]

f(k) - f(k-1) = nums[1] + nums[2] + ... nums[n-1]. - (n-1)*nums[0]
 
 = sum - n*nums[0]
 => f(k) = f(k-1) + sum - n*nums[0]

 k = 1 -> sum - n*nums[len-1]
 k = 2 -> sum - n*nums[len-2]
 ...

 anyway, we can calculate sum first


F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
---------


latest update:

more concise way: 

list f(1) - f(0)
list f(2) - f(1)
list f(3) - f(2)
list f(4) - f(3) ...

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16

num[0] + num[1] + num[2] - (n-1)*num[3]

we can find...
f(1) = f(0) + num[0] + num[1] + num[2] - (n-1)*num[3] 
     = f(0) + sum - n*num[3]

f(2) = f(1) + ... -  (n-1)*num[2]
     = f(1) + sum - n*num[2]    

f(3) = f(2) + ... -  (n-1)*num[1]
     = f(2) + sum - n*num[1]       

f(4) = f(3) + ... -  (n-1)*num[0]
     = f(3) + sum - n*num[0]          

f(k) = f(k-1) + sum - n*num[n-k]     
  */
```