leetcode [#396]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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).

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.

Note:

• n is guaranteed to be less than 10^5.

---

解决方案

public class Solution {
    public int maxRotateFunction(int[] A) {
        int N = A.length;
        if(A == null || N == 0) return 0;

        int sum = 0;
        int f0 = 0;

        for(int t = 0; t < N; t++){
            sum += A[t];
            f0 += t * A[t];
        }

        int max = f0;

        for(int p = 1; p < N; p++){
            f0 = f0 - sum + N * A[p-1];
            max = f0 > max ? f0 : max;
        }
        return max;
    }
}

---

注意事项

1.使用如下方法会超时：

public static int maxRotateFunction(int[] A) {
    if(A == null || A.length == 0) return 0;

    int N = A.length;
    int[] F = new int[N];

    for(int k = 0; k < N; k++){
        F[k] = 0;

        for(int j = 0; j < N; j++){
            int index = ((N-k) % N + j) < N ? ((N-k) % N + j) : (((N-k) % N + j) % N);
            F[k] = F[k] + j * A[index];
        }
    }
    Arrays.sort(F);
    return F[N-1];
}

　　该方法只是严格按照运算规则逐一进行了运算，但没有找到实际规律，导致大量无用的计算。

2.应该采用的做法中，找到了F函数相邻两项的规律，即：后一项F(i)是在前一项F(i-1)的基础上，减去输入数组之和sum，再加上数组长度N乘以A[i-1]。