396. Rotation function

396. Rotation function

Answer key

subject ： Give an array , Calculation f,f= Subscript * value Accumulation , Each time the number of the array is moved to the end of the front , For the biggest f

Ideas ：

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

f(0)=0*nums[0]+1*nums[1]+2*nums[2]+...+(n-1)*nums[n-1]
f(1)=1*nums[0]+2*nums[1]+3*nums[2]+...+0*nums[n-1]

f(1)-f(0)=nums[0]+nums[1]+nums[2]-(n-1)*nums[n-1]
         =nums[0]+nums[1]+nums[2]+nums[n-1]-n*nums[n-1]

 set up numSum=nums[0]+...+nums[n-1]
 have to f(1)-f(0)=numSum-n*nums[n-1]

 Get the general formula f(i)-f(i-1)=numSum-n*nums[n-i]
f(i)=f(i-1)+numSum-n*nums[n-k]

Code

func maxRotateFunction(nums []int) int {
    
	numSum, f, n := 0, 0, len(nums)
	for i, v := range nums {
    
		numSum += v
		f += i * v
	}
	//numSum=nums[0]+...+nums[n-1]
	//f(i)=f(i-1)+numSum-n*nums[n-i]
	ans := f
	for i := 1; i < len(nums); i++ {
    
		f = f + numSum - n*nums[n-i]
		ans = max(ans, f)
	}
	return ans
}
func max(i, j int) int {
    
	if i > j {
    
		return i
	}
	return j
}