c++ O(n) solution


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

Log in to reply
 

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