原题链接

https://leetcode.com/problems/rotate-function/

原题

Given an array of integers A and let n to be its length. Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow: F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1]. Calculate the maximum value of F(0), F(1), …, F(n-1).

Note: n is guaranteed to be less than 105.

Example:

A = [4, 3, 2, 6] 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 So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

题目要求

题目叫“旋转函数”（不知道这个翻译是否合适），给定一个数组（数组长度为n），按照F(k)函数的格式求值，然后再将数组位置都向前旋转进一位，比如索引为0的值放到索引为1的位置，1到2，2到3，而n-1则因为越界，排到第0的位置。这样的旋转进行n次，每次都算出F(k)的值，然后求出最大值。 编写测试用例时，需要注意数组为空、数组元素为负时等一些情况。

解法

解法一：直接按照给定的公式，分别计算每个F(k)的值。这种算法的时间复杂度是O(n平方），当n较大时，会超时。

public int maxRotateFunction(int[] A) { if (A.length == 0) { return 0; } int max = Integer.MIN_VALUE; for (int i = 0, k = 0; i < A.length; i++, k++) { int temp = 0; for (int j = 0; j < A.length; j++) { temp += j * A[(j - k + A.length) % A.length]; } max = (max < temp) ? temp : max; } return max; }

解法二：动态规划法。为了降低时间复杂度，我们需要想点其他的方法，对比给出的示例，F(0)与F(1)的区别，就是F(0)中除了A[n-1]之外，其他的数字都增加了一倍，并且还要再减去（n-1）*A[n-1]，F[0]就是增加了4，3，2，然后再减去了3*6，F[1] = F[0] + 4 + 3 + 2 - 3 * 6 = 16。因此我们可以求出这样一个公式： F[n] = F[n - 1] + (sum - A[sumIndex]) - (A.length - 1) * A[sumIndex] 其中，sumIndex = -n + A.length，即旋转时要从索引n-1移动到0的那个值。sum为数组A中所有值的和，而(sum - A[sumIndex]) 自然就是数组A中除了索引为sumIndex之外其他所有值的和。 这种解法的时间复杂度是O(n)。

public int maxRotateFunction(int[] A) { int sum = 0; // 计算出sum for (int i = 0; i < A.length; i++) { sum += A[i]; } int base = 0; // 计算出F[0]的值 for (int i = 0; i < A.length; i++) { base += i * A[i]; } int max = base; for (int i = 1; i < A.length; i++) { int sumIndex = -i + A.length; // 公式展开后，得出如下 base += sum - A.length * A[sumIndex]; // base += (sum - A[sumIndex]) - (A.length - 1) * A[sumIndex]; max = (max < base) ? base : max; } return max; }

测试用例：

public static void main(String[] args) { Solution s = new Solution(); { int []A = new int[]{}; assert(s.maxRotateFunction(A) == 0); } { int []A = new int[]{4, 3, 2, 6}; assert(s.maxRotateFunction(A) == 26); } { int []A = new int[]{-1}; assert(s.maxRotateFunction(A) == 0); } { int size = 65535; int []A = new int[size]; for (int i = 0; i < size; i++) { A[i] = i - 3; } assert(s.maxRotateFunction(A) == 2147408563); } }