C++ 9ms Solution With Concise Explanation


  • 0
    G

    The idea is very simple. We only calculate the difference between two iterations. Try to write in math expression as below:
    F(k) = F(k - 1) + ( sum(A) - A.size() * A(the last element in A after rotate k - 1 positions.))

    Let's take an example . A = [4, 3, 2, 6]

    First, calculate sum(A) = 4 + 3 + 2 + 6 =15

    And F[0] = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25

    Then we begin to rotate. F[1] = F[0] + (sum(A) - A.size() * 6) = 25 + (15 - 4 * 6) = 16

    And F[2] = F[1] + (sum(A) - A.size() * 2) = 16 + (15 - 8) = 23 (2is the last element of A after rotate A for k - 1 = 1 position)

    Since we can calculate sum, F[0] in O(n) time. And then we get F[k]from F[k - 1using O(1) time, the total time complexity is O(n).

    Here is my AC code. Hope it helps.

    class Solution {
    public:
        int maxRotateFunction(vector<int>& A) {
            if (A.size() == 0) return 0;
            int sum = 0, current = 0;
            for(int i = 0; i < A.size(); ++i) {
                sum+= A[i];
                current+= i * A[i];
            }
            int maximum = INT_MIN;
            for (int i = A.size() - 1; i >=0; --i) {
                current+= sum - A.size() * A[i];
                maximum = max(maximum, current);
            }
            return maximum;
        }
    };
    

Log in to reply
 

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