旋转函数
难度：中等
首先尝试用暴力破解，模拟过程
代码如下：
public class RotateFunction{
int len;
int[] nums ;
public int maxRotateFunction(int[] _nums) {
int res = Integer.MIN_VALUE;
nums = _nums;
len = nums.length;
for (int i = 0; i < nums.length; i++) {
System.out.println(getResult(i));
res = Math.max(res,getResult(i));
}
return res;
}
public int getResult(int i){
int cnt = 0;
for (int j = 0; j < len; j++) {
cnt+= j*nums[i];
if (i==len-1){
i=0;
}else{
i++;
}
}
return cnt;
}
}
果然TLE了。。
翻翻题解，其实应该利用数学求解。
记数组 nums 的元素之和为 numSum。根据公式，可以得到：
F(0)=0×nums[0]+1×nums[1]+…+(n?1)×nums[n?1]
F(1)=1×nums[0]+2×nums[1]+…+0×nums[n?1]
=F(0)+numSum?n×nums[n?1]
更一般地，当 1≤k<n 时，F(k)=F(k?1)+numSum?n×nums[n?k]。我们可以不停迭代计算出不同的 F(k)，并求出最大值。
用更通俗的话讲：向右旋转一次，就相当于把当前结果加上整个数组的和，再减去数组大小乘以当前最后一位。
public int maxRotateFunction1(int[] nums) {
int res = 0;
//记录nums中的元素之和
int cnt = 0;
int len = nums.length;
int[] sum = new int[len];
for (int i = 0; i < len; i++) {
cnt += nums[i];
sum[0] += i* nums[i];
}
res = sum[0];
for (int i = 1; i < len; i++) {
sum[i] = sum[i-1] + cnt - len * nums[len-i];
res = Math.max(res,sum[i]);
}
return res;
}
