Java Solution with O(n) in 5ms


  • 0
    Z

    Step1: Get sum of A[n]----arrSum.
    Step2: Find the max sum in a n-for loop.
    In the n-for loop, every step's sum is: Lastsum - (n-1) * Bk[n-1] + (arrSum-Bk[0])

    public int maxRotateFunction(int[] A) {
        if(A==null||A.length==0)
            return 0;
    
    
        int len=A.length;
        int arrSum=0;
        int lastSum=0;
        for(int i=0;i<len;++i){
            arrSum+=A[i];
            lastSum+=(i*A[i]);
        }
    
    
        int max=lastSum;
        for(int i=1;i<len;++i) {
            lastSum=lastSum-A[len-i]*(len-1)+(arrSum-A[len-i]);
            max=max>lastSum?max:lastSum;
        }
    
        return max;
    }

Log in to reply
 

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