Java O(n) solution with explanation


  • 106
    O
    F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]
    F(k-1) = 0 * Bk-1[0] + 1 * Bk-1[1] + ... + (n-1) * Bk-1[n-1]
           = 0 * Bk[1] + 1 * Bk[2] + ... + (n-2) * Bk[n-1] + (n-1) * Bk[0]
    

    Then,

    F(k) - F(k-1) = Bk[1] + Bk[2] + ... + Bk[n-1] + (1-n)Bk[0]
                  = (Bk[0] + ... + Bk[n-1]) - nBk[0]
                  = sum - nBk[0]
    

    Thus,

    F(k) = F(k-1) + sum - nBk[0]
    

    What is Bk[0]?

    k = 0; B[0] = A[0];
    k = 1; B[0] = A[len-1];
    k = 2; B[0] = A[len-2];
    ...
    
    int allSum = 0;
    int len = A.length;
    int F = 0;
    for (int i = 0; i < len; i++) {
        F += i * A[i];
        allSum += A[i];
    }
    int max = F;
    for (int i = len - 1; i >= 1; i--) {
        F = F + allSum - len * A[i];
        max = Math.max(F, max);
    }
    return max;   
    

  • 7
    S
    • Explanation:
      F(k) = 0 * Bk[0-k] + 1 * Bk[1-k] + ... + (n-1) * Bk[n-1-k]
      F(k+1) = 0 * Bk[n-(k+1)] + 1 * Bk[1-(k+1)] + ... + (n-2) * Bk[n-1-(k+1)]
      = 0 * Bk[n- 1 - k] + 1 * Bk[0-k] + ... + (n-2) * Bk[n-2-k]
      = 0 * Bk[0-k] + 1 * Bk[1-k] + ... + (n-1) * Bk[n-1-k] + sum - n *Bk[n-(k+1)]
      Note: Bk[n- 1 - k] == Bk[n-(k+1)]
      Then,

      F(k+1) - F(k) = Bk[0-k] + Bk[1-k] + ... + Bk[n-2-k] - (n-1)Bk[n-(k+1)]
                                    = (Bk[0] + ... + Bk[n-1]) - n*Bk[n-(k+1)]
                                    = sum - n*Bk[n-(k+1)]
      
      Thus,
      
      F(k) = F(k-1) + sum - n* Bk[n-k]

  • 3
    F

    Thanks for the post. It is really a beautiful solution.

    However, I think the above deductions may have some flaws. Because we cannot get the F(0) from F(k). Personally I would use only
    the base case, k = 0

    F(0) = 0 * Bk[0] + 1 * Bk[1] + ... + (n - 1) * Bk[n - 1]
    

    and the case when k > 0 and k < n

    F(k) = 0 * Bk[n - k] + 1 * Bk[n - k + 1] + ... + (n - 1) * Bk[n - (k + 1)]
    

    For those who got confused why we will start from i = len - 1:

    F(1) = F(0) + sum - n * A[n - 1], here n = len so that A[n - 1] == A[i]
    F(2) = F(1) + sum - n * A[n - 2]
    ...
    F(k) = F(k - 1) + sum - n * A[n - k]
    

    Why we will end if i < 1? It's because we deduced k < n and k > 0. So that it's obviousn - k > 0, which means i > 0.

    Hope this will help a little bit to understand this nice post.


  • 1
    S

    @Free9
    No need start from i = len - 1 and it will confuse some other ppl.
    Thus, we should start with k = 1 till k = len -1.

    See my Explanation:
    F(k) = 0 * Bk[0-k] + 1 * Bk[1-k] + ... + (n-1) * Bk[n-1-k]
    F(k+1) = 0 * Bk[n-(k+1)] + 1 * Bk[1-(k+1)] + ... + (n-2) * Bk[n-1-(k+1)]
    = 0 * Bk[n- 1 - k] + 1 * Bk[0-k] + ... + (n-2) * Bk[n-2-k]
    = 0 * Bk[0-k] + 1 * Bk[1-k] + ... + (n-1) * Bk[n-1-k] + sum - n *Bk[n-(k+1)]

    Note: Bk[n- 1 - k] == Bk[n-(k+1)]
    Then,

    F(k+1) - F(k) = Bk[0-k] + Bk[1-k] + ... + Bk[n-2-k] - (n-1)Bk[n-(k+1)]
    = (Bk[0] + ... + Bk[n-1]) - nBk[n-(k+1)]
    = sum - n
    Bk[n-(k+1)]

    Thus,

    F(k) = F(k-1) + sum - n* Bk[n-k]

    Code change a little bit:
    int allSum = 0;
    int len = A.length;
    int F = 0;
    for (int i = 0; i < len; i++) {
    F += i * A[i];
    allSum += A[i];
    }
    int max = F;
    for (int k = 1; k < len; k++) {
    F = F + allSum - len * A[len - k];
    max = Math.max(F, max);
    }
    return max;


  • 0
    H

    Great solution. Two critical paths:

    • The relationship between F(k) and F(k-1), build the DP function
    F(k) = F(k-1) + sum - n * Bk[0]
    
    • The relationship bettwen Bk[0] with A[i]

    Thanks!


  • 0

    @swzheng0418 Format your code please!!


  • 0

    came up with the same solution with c#,

    public class Solution {
        public int MaxRotateFunction(int[] A) {
            if (A == null) {
                return 0;
            }
            
            int current = 0;
            int sum = 0;
            
            for(int i = 0; i < A.Length; i++) {
                current += i * A[i];
                sum += A[i];
            }
            
            int max = current;
            
            for(int i = A.Length - 1; i >= 1; i--) {
                current = current + sum - A.Length * A[i];
                max = Math.Max(max, current);
            }
            
            return max;
        }
    }
    

  • 0
    H
    This post is deleted!

  • 0
    W

    What the means of rotating the array A k positions clock-wise


  • 0
    T

    Thanks For sharing!!!

    public class Solution {
        public int maxRotateFunction(int[] A) {
            if(A==null||A.length<1) return 0;
            
            int sum=0;
            int t_pre=0;
            for(int i=0;i<A.length;i++){
                sum+=A[i];
                t_pre+=i*A[i];
            }
            
            
            int max=t_pre;
            for(int i=A.length-1;i>=1;i--){
                int current=t_pre+sum-A.length*A[i];
                max=Math.max(max,current);
                t_pre=current;
            }
            return max;
        }
    }
    

Log in to reply
 

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