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 += vf += i * v}//numSum=nums[0]+...+nums[n-1]//f(i)=f(i-1)+numSum-n*nums[n-i]ans := ffor 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
}