Force deduction solution summary 396 rotation function

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Given a length of n Array of integers for  nums .

hypothesis  arrk  It's an array  nums  Clockwise rotation k Array after position , We define  nums  Of Rotation function   F  by ：

F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]
return  F(0), F(1), ..., F(n-1) Maximum of  .

The generated test cases make the answers meet the requirements  32 position Integers .

Example 1:

Input : nums = [4,3,2,6]
Output : 26
explain :
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
therefore F(0), F(1), F(2), F(3) The maximum value in is F(3) = 26 .
Example 2:

Input : nums = [100]
Output : 0
 

Tips :

n == nums.length
1 <= n <= 105
-100 <= nums[i] <= 100

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/rotate-function
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  If the simple implementation logic is very simple , But the length of the array is 10W, If we calculate according to the requirements , Need 10W*10W Amount of computation ,O(n2) Time complexity of , Then it will time out .
*  Therefore, the core is to reduce the time complexity to O(n) Level , So we can try to find rules .
*  This law is for each different function , The change of its summation is regular . For example, in the example 1 in ,F(0) and F(1).
* nums = [4,3,2,6]
* 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
*  We can think of it this way ,F(1)=F(0)+(4+3+2)-3*6=16
*  So the law is obvious , Just add all the numbers each time ( Not including the last ), Then subtract the last number and multiply by (nums.length - 1) that will do .

Code ：

public class Solution396 {

    public int maxRotateFunction(int[] nums) {
        int f = 1;
        int sum = 0;
        int currentFK = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            currentFK += i * nums[i];
        }
        int maxFK = currentFK;
        while (f < nums.length) {
            int lastValue = nums[nums.length - f];
            currentFK = currentFK + (sum - lastValue) - lastValue * (nums.length - 1);
            maxFK = Math.max(currentFK, maxFK);
            f++;
        }

        return maxFK;
    }
}