clean O(n) C++ solution


  • 2
    A
    class Solution {
    public:
        int maxRotateFunction(vector<int>& A) {
            if (A.empty())
                return 0;
            
            int s = 0, candidate = 0, n = A.size();
            for (int i = 0; i < n; ++i) {
                s += A[i];
                candidate += i * A[i];
            }
            
            int ans = candidate;
            for (int i = n - 1; i > 0; --i) {
                candidate += s - n * A[i];
                ans = max(ans, candidate);
            }
            return ans;
        }
    };
    

Log in to reply
 

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