“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Happy New Year everyone! Today is the first day of the Chinese New Year, I wish you all in the New Year dragon teng Tiger jump, Tiger Tiger live. Continue to work on leetcode topics, select some medium difficulty today, and make progress slowly in the New Year.

The title

Given an array of integers A of length N. Assuming that Bk is the array of array A rotated clockwise by k positions, we define the “rotation function” F of A as: F(k) = 0 * Bk[0] + 1 * Bk[1] +… Plus n minus 1 Bk times n minus 1. Calculate F(0), F(1)… F(n-1).

Note: the value of n can be considered 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 times 4 is 0 plus 2 plus 12 plus 12 is 26 so the maximum value in F(0), F(1), F(2), F(3) is 26.

Train of thought

So if we rotate clockwise, we’re going to put the last element in the array first, and we’re not going to change the order of the other elements. When the array is large, each recalculation is expensive, so our goal is either to directly identify where the maximum occurs, or to find a way to quickly compute f(k). Num [0] ~ num[n-1]; n is the length of the array: f(k+1) = f(k+1);

f(k) = 0 * num[0] + 1 * num[1] +… + (n-2) * num[n-2] + (n-1) * num[n-1] f(k+1) = 0 * num[n-1] + 1 * num[0] + 2 * num[1] +… + (n-2) * num[n-3] + (n-1) * num[n-2]

F of k plus 1 minus f of k, and notice that you can subtract from the right side

f(k+1) – f(k) = num[0] + num[1] +… + num[n-2] – (n-1) * num[n-1] = num[0] + num[1] +… + num[n-2] – (n * num[n-1] – num[n-1]) = num[0] + num[1] +… + num[n-2] + num[n-1] – n * num[n-1] = sum – n * num[n-1]

So, we can get a fast solution for f of k plus 1

f(k+1) = f(k) + sum – n * num[n-1]

In this case, we can initially solve sum and f(0), then use the above formula to solve f(1) ~ f(n-1), and then compare the maximum value.

Java version code

class Solution { public int maxRotateFunction(int[] nums) { int len = nums.length; int ans = 0; int current = 0; int sum = 0; // sum for (int I = 0; i < len; i++) { sum += nums[i]; current += i * nums[i]; } ans = current; For (int I = len-1; int I = len-1; int I = len-1; i > 0; i--) { current = current + sum - len * nums[i]; ans = Integer.max(ans, current); } return ans; }}Copy the code