给定一个长度为 n 的整数数组 nums 。 假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组,我们定义 nums 的 旋转函数 F 为:
返回 F(0), F(1), …, F(n-1)中的最大值 。 生成的测试用例让答案符合 32 位 整数。
示例 1: 输入: nums = [4,3,2,6] 输出: 26 解释:
// k=0 顺时针旋转0个位置 arr0=[4,3,2,6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
// k=1 顺时针旋转1个位置 arr1=[6,4,3,2]
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
// k=2 顺时针旋转2个位置 arr2=[2,6,4,3]
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
// k=3 顺时针旋转3个位置 arr3=[3,2,6,4]
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 。
采用双指针,一头一尾,每旋转一次,两个指针左移便是旋转后的切片。
func maxRotateFunction(nums []int) int {
length := len(nums)
if length==1 {
return 0
}
// 每轮两指针左移一位
pointHead := 0
pointTail := length - 1
ans := math.MinInt64
for i := 0; i < length; i++ {
f := 0
head := pointHead
for j := 0; j < length; j++ {
f = j*nums[head] + f
head = (head + 1) % length
}
// 如果头指针后推,为负,就指向队列末尾
pointHead--
if pointHead < 0 {
pointHead = length - 1
}
pointTail--
ans = int(math.Max(float64(ans),float64(f)))
}
return ans
}
观察F(0), …, F(k)的规律可得: 每旋转一次数组,都是最后一个值的系数变为了0,而其他值的系数都是+1 所以定义sum用来存放数组和, 而
F(k)+sum
就等于所有系数都+1, 再减去最后一个变化后的值去掉就就是F(k+1)
的值了 以示例1为例:
F(1) = (1 * 4) + (2 * 3) + (3 * 2)+ (0 * 6)
F(0)+sum = (1 * 4) + (2 * 3) + (3 * 2) + (4 * 6)
可以看到原本最后一个值应该对应的是0*6 而F(0)+sum里却是4*6
所以我们可以得出:
F(1) = F(0) + sum - 最后一个变化后的值 = 25 + 15 - 24 = 16func maxRotateFunction(nums []int) int {
// sum: 数组内所有元素的和
// curSum: F(k) 就是每次旋转数组后,代入F(k)公式求的那个
sum, curSum, ans := 0, 0, 0
for i := 0; i < len(nums); i++ {
// 求数组和
sum = sum + nums[i]
// 求F(0)
curSum = curSum + i*nums[i]
}
ans = curSum
for i := len(nums) - 1; i > 0; i-- {
// F(K+1) = F(K) + sum - 最后一个变化后的值
curSum = curSum + sum - len(nums)*nums[i]
ans = max(ans, curSum)
}
return ans
}
func max(a, b int) int {
if b > a {
return b
}
return a
}