subject

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 <= 10⁵
-100 <= nums[i] <= 100

Code

package dayLeetCode;

public class dayleetcode396 {
    
    /** * *  The mathematical formula   Classical mathematical problems , See that the first and second terms change only in constants , Then we can find the relationship between the first two through calculation  * F(0) = 0 * nums[0] + 1 * nums[1] + ... + (n - 1) * nums[n - 1] * F(1) = 1 * nums[0] + 2 * nums[1] + ... + (n - 1) * nums[n - 2] + 0 * nums[n - 1] * = (nums[0] + nums[1] + ... + nums[n-1] - nums[n-1]) + (0 * nums[0] + 1 * nums[1] + ... +(n - 1) * nums[n -1]) -(n -1)*nums[n-1] * = sum + F(0) - n * nums[n-1]  among sum Is an array nums The sum of the elements of  * F(2) = 2 * nums[0] + ... + 0*nums[n-2] + 1*nums[n-1] * = sum + F(1) - n * nums[n-2] * *  therefore F(t) = f(t-1)+ sum - n*nums[n-t] * @param nums * @return */
    public int maxRotateFunction(int[] nums) {
    
        int sum = 0;
        for (int n : nums){
    
            sum += n;
        }
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++){
    
            dp[0] += (i * nums[i]);
        }

        int ans = dp[0];
        for (int i = 1; i < nums.length; i++){
    
            dp[i] = dp[i - 1] + sum - nums.length * nums[nums.length - i];
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }

    public static void main(String[] args) {
    
        dayleetcode396 obj = new dayleetcode396();
        int[] nums = {
    4, 3, 2, 6};
        System.out.println(obj.maxRotateFunction(nums));
    }
}