Simple c solution [O(n) time and O(1) space]


  • 2
    R

    The naive approach is rotate the array each time 1 place left/right, get the indexed sum and determine max. But it will take O(n^2).
    U
    But with some simulation you will find that the result of one rotation can be foumd from its previous rotation. The formula is

    newsum = prevsum + allsum - ASize*A[i]
    

    I used to rotate the array to right by one place. Rotate the array to one place right means rotating the indexes to one place left.

    int maxRotateFunction(int* A, int ASize) {
        int i, last, sum,m;
        
        if(ASize<=1) return 0;
        
        last=0;
        sum=0;
        for(i=0;i<ASize;i++){
            last += A[i]*i;
            sum+=A[i];
        }
        m=last ;
        for(i=ASize-1;i>=1;i--){
            last += sum - (ASize*A[i]);
            if (last > m) m= last;
        }
        
        return m;
    }
    

Log in to reply
 

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