Open Shawngbk opened 7 years ago
不妨设想，所有数组元素向右移动一位会和会发生什么变化，结果我们可以看到，除了最后一位元素，所有元素的权重值都加了1，也就是和多加了A[0]+A[1]+...+A[N-2]，而对于最后一位元素，被移到最前面，也就是A[n-1]的权重从（n-1）变成了0， 因此和减少了 （n-1）*A[n-1]
所以说，每一次移动的和S(new)，和相对于上一次移动的和S(old)的关系如下：
S(new) = S(old) + { S - A[n-1] - (n-1)_A[n-1] } = S(old) + { S - n_A[n-1] }; // S = A[0]+A[2]+A[3]+...+A[n]
因此，每顺时针移动一位，只需要进行一次计算就好。 public class Solution { public int maxRotateFunction(int[] A) { int n = A.length; if(n == 0) return 0; int preSum = 0; int sumA = 0; for(int i = 0; i < n; i++) { // sumA = A[0] + A[1] +...+A[n-1] sumA += A[i]; preSum += i * A[i]; } int maxSum = preSum; for(int i = n-1; i >= 0; i--) { // S(new) = S(old) + { S - n_A[i] }; preSum += sumA - n_A[i]; maxSum = Math.max(maxSum, preSum); } return maxSum; } }
Amazon
Shawngbk
commented
7 years ago Shawngbk
commented
7 years ago
不妨设想，所有数组元素向右移动一位会和会发生什么变化，结果我们可以看到，除了最后一位元素，所有元素的权重值都加了1，也就是和多加了A[0]+A[1]+...+A[N-2]，而对于最后一位元素，被移到最前面，也就是A[n-1]的权重从（n-1）变成了0， 因此和减少了 （n-1）*A[n-1]
所以说，每一次移动的和S(new)，和相对于上一次移动的和S(old)的关系如下：
S(new) = S(old) + { S - A[n-1] - (n-1)_A[n-1] } = S(old) + { S - n_A[n-1] }; // S = A[0]+A[2]+A[3]+...+A[n]
因此，每顺时针移动一位，只需要进行一次计算就好。 public class Solution { public int maxRotateFunction(int[] A) { int n = A.length; if(n == 0) return 0; int preSum = 0; int sumA = 0; for(int i = 0; i < n; i++) { // sumA = A[0] + A[1] +...+A[n-1]
sumA += A[i]; preSum += i * A[i]; } int maxSum = preSum; for(int i = n-1; i >= 0; i--) { // S(new) = S(old) + { S - n_A[i] }; preSum += sumA - n_A[i]; maxSum = Math.max(maxSum, preSum); } return maxSum; } }