396.旋转函数

396.旋转函数

题解

题目：给一个数组，计算f，f=下标*值 的累加，并且每次会把数组末尾的数移到前面，求最大的f

思路：

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]

设numSum=nums[0]+...+nums[n-1]
得f(1)-f(0)=numSum-n*nums[n-1]

得到通式f(i)-f(i-1)=numSum-n*nums[n-i]
f(i)=f(i-1)+numSum-n*nums[n-k]

代码

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
}