My easy java solution


  • 0
    Z

    It is easy to find out the form of F(k) - F(0):
    F(k) - F(0) = k * Sum(i for i in A) - n * (A[n-k] + A[n-k+1] + ... + A[n-1]),
    where n is the length of A. Thus we do not need to use extra arrays to implement this project. However, the first time I used int-type variables, but I got errors. Then I instead used long-type variables and it worked out fine. Here is the code.

    public class Solution {
        public int maxRotateFunction(int[] A) 
        {
            long a = 0, b = 0, res = 0, t = 0, f0 = 0;
            int n = A.length;
            for (int i = 0; i < n; i++) 
            {
                a += A[i];
                f0 += i * A[i];
            }
            for (int k = 1; k < n; k++)
            {
                b += A[n - k];
                t = k * a - n * b;
                res = t > res ? t : res;
            }
            return (int)(f0 + res);
        }
    

  • 0
    L

    F(k) - F(0) = k * Sum(i for i in A) - n * (A[n-k] + A[n-k+1] + ... + A[n-1]),
    i think it should be F(k) - F(0) = k * Sum(i for i in A) - n * (A[n-k] + A[n-k-1] + ... + A[1]).
    am i right?


  • 0
    Z

    @lianglinMan
    I don't think so. Let's have a look.

    Fk = Sum(i * Bki) and Fk-1 = Sum(i * Bk-1i), i from 0 to n-1.

    Since Bki+1 = Bk-1i, we could find that:
    Fk - Fk-1 = (Bk1 + Bk2 + ... + Bkn-1) - (n-1)Bk-1n-1

    = (Bk1 + Bk2 + ... + Bkn-1) - (n-1)Bk0

    = Sum(i for i in A) - nBk0

    Thus:
    Fk - F0 = k * Sum(i for i in A) - n(B10 + B20 + ... + Bk0)

    = k * Sum(i for i in A) - n(An-1 + An-2 + ... + An-k)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.