C# - same solution but different take on explaination


  • 5

    To me it is easier to see the solution if you leave the array as is and rotate the factors left (same result as rotating array right).

    For simplicity take an array with 4 elements
    [a,b,c,d]

    f(0) = 0a + 1b + 2c +3d
    f(1) = 3a + 0b + 1c +2d
    f(2) = 2a + 3b + 0c +1d
    f(3) = 1a + 2b + 3c +0d

    Now look what happens when you take difference between f(k) - f(k-1)
    f(1) - f(0) = 3a - b - c - d = 4a - (a + b + c + d) = length * a - sum
    f(2) - f(1) = -a + 3b - c - d = 4b - (a + b + c + d) = length * b - sum
    f(3) - f(2) = -a - b +3c - d = 4c - (a + b + c + d) = length * c - sum

    You can see if you calculate (manually) f(0) you can get f(1) by adding length * a and subtracting the sum.

    So initially you need to compute the sum and f(0) then just iterate through and get the value of f(i) for each i and record the max.

    Hope that helps!

    public int MaxRotateFunction(int[] A) {
        
        int sum = 0;
        for (int i = 0; i < A.Length; i++) sum += A[i];
        
        int prev = 0;
        for (int i = 0; i < A.Length; i++) prev += i * A[i];
        
        int max = prev;
        for (int i = 1; i < A.Length; i++)
        {
            int curr = prev - sum + A[i-1]*A.Length;
            max = curr > max ? curr : max;
            prev = curr;
        }
        
        return max;
    }

Log in to reply
 

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