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 }
