1.题目
给定一个长度为 n 的整数数组 nums 。
假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数 F 为：
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]
返回 F(0), F(1), …, F(n-1)中的最大值 。
生成的测试用例让答案符合 32 位 整数。
2.示例
示例 1:
输入: nums = [4,3,2,6]
输出: 26
解释:
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2)= (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。
示例 2:
输入: nums = [100]
输出: 0
提示:
n == nums.length
1 <= n <= 105
-100 <= nums[i] <= 100
3.思路
错误思路：
题目怎么说就直接去实现，按照题目的逻辑去解决题目的问题。这种观念有时要避免，因为很容易超时
我的代码如下，一如既往的通俗易懂，就不多做解释，代码里有简单的注释
func maxRotateFunction(nums []int) int { var answer int //遍历每一次旋转 for i:=0; i < len(nums); i++ { if len(nums) == 1 { return 0 } //一次旋转 head := nums[len(nums)-i:] tail := nums[:len(nums)-i] hall := append(head, tail...) //得到一次旋转的结果，还要再次遍历 var part int for j := 0; j < len(hall); j++{ part = part + j*hall[j] } //这里是因为answer初始值为0，旋转结果全为负数时，结果错误 if i == 0{ answer = part } answer = max(answer, part) } return answer } //前几天每次碰到取最大值时官方都会单独写一个函数，这次我也写了。 //听过一个课说这样写有利于复用啥的，虽然只调用了一次，不过以后都这样写了，有利无害。 func max(a, b int) int{ if b > a { return b } return a }
正确思路：
对于算法问题不一定要完全按照实际问题的逻辑去解决。回想以前，通过找规律的方法巧妙的解决了问题的情况遇到过也不只一次。这次就是
观察规律可以发现，除了黄色部分的数字以外，每一个乘数都比上面的乘数少一。所以
f(1) = f(0) - ( num1 + num2 + num3 + num4 + num5 ) + 5*num1
找到这个规律以后这个题就很简单了，代码如下
4.代码
func maxRotateFunction(nums []int) int { var answer int var stair int for _,v:=range nums{ stair=stair+v } //先计算出f（0） var temp int for i,v:= range nums{ temp = temp + i * v } for i,v:=range nums{ if len(nums) == 1 { return 0 } if i == 0 { answer = temp } //找到的规律 temp = temp - stair + len(nums) * v answer = max(answer, temp) } return answer } func max(a, b int) int{ if b > a { return b } return a }
5.复杂度分析
时间复杂度O(n);
空间复杂度O(1)。
