C++ solution O(n)


  • 0
    H

    The main idea is find the relation between f[k],f[k+1]

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

Log in to reply
 

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