396. Rotation function

Title Description ：

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(k) = 0 * arrk[0] + 1 * arrk[1] + … + (n - 1) * arrk[n - 1]

// k=0  Clockwise rotation 0 A place  arr0=[4,3,2,6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 
// k=1  Clockwise rotation 1 A place  arr1=[6,4,3,2]
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
// k=2  Clockwise rotation 2 A place  arr2=[2,6,4,3]
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
// k=3  Clockwise rotation 3 A place  arr3=[3,2,6,4]
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 .

Timeout solution ：

Ideas ：

Use double pointer , One end and one tail , Every rotation , Moving the two pointers to the left is the rotated slice .

func maxRotateFunction(nums []int) int {
    
	length := len(nums)
	if length==1 {
    
		return 0
	}
	//  Two hands move one bit to the left in each round 
	pointHead := 0
	pointTail := length - 1
	ans := math.MinInt64
	for i := 0; i < length; i++ {
    
		f := 0
		head := pointHead
		for j := 0; j < length; j++ {
    
			f = j*nums[head] + f
			head = (head + 1) % length
		}
		//  If the head pointer pushes back , Negative , Just point to the end of the queue 
		pointHead--
		if pointHead < 0 {
    
			pointHead = length - 1
		}
		pointTail--
		ans = int(math.Max(float64(ans),float64(f)))
	}
	return ans
}

Positive solution ：

Ideas ：

Observe F(0), …, F(k) The law of is available ：
  Every time you rotate the array , The coefficient of the last value becomes 0, The coefficients of other values are +1
So define sum Used to store arrays and , and F(k)+sum That's equal to all the coefficients +1, Then subtract the value after the last change and remove it, that's F(k+1) The value of the

By way of example 1 For example ：

• sum Is the sum of all the elements in the slice , Every time you add sum, Equivalent to F(k) Every coefficient of is +1
  for example ：
   sum = 4 + 3 + 2 + 6 = 15
   F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
   F(0)+sum = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6)+ 4 + 3 + 2 + 6
        = (1 * 4) + (2 * 3) + (3 * 2) + (4 * 6) = 40
  And the law observed above ： Every time you rotate the array , The coefficient of the last value becomes 0, The coefficients of other values are +1
  Then we observe F(1) Relative to F(0)+sum What's the difference ：
   F(1) = (1 * 4) + (2 * 3) + (3 * 2)+ (0 * 6)
 F(0)+sum = (1 * 4) + (2 * 3) + (3 * 2) + (4 * 6)
  You can see that the last value should correspond to 0*6 and F(0)+sum But inside 4*6
  So we can figure out ：
  F(1) = F(0) + sum - The value after the last change = 25 + 15 - 24 = 16

func maxRotateFunction(nums []int) int {
    
	// sum:  The sum of all elements in the array 
	// curSum: F(k)  Every time you rotate the array , Plug in F(k) The one from the formula 
	sum, curSum, ans := 0, 0, 0
	for i := 0; i < len(nums); i++ {
    
		//  Sum arrays 
		sum = sum + nums[i]
		//  seek F(0)
		curSum = curSum + i*nums[i]
	}
	ans = curSum
	for i := len(nums) - 1; i > 0; i-- {
    
		// F(K+1) = F(K) + sum -  The value after the last change 
		curSum = curSum + sum - len(nums)*nums[i]
		ans = max(ans, curSum)
	}
	return ans
}

func max(a, b int) int {
    
	if b > a {
    
		return b
	}
	return a
}

Submit results ：