Java Solution


  • 3
    D

    This is essentially a Math problem.
    Consider the array [ A, B, C, D ] with very simple coefficients as following:

    f(0) = 0A + 1B + 2C + 3D
    f(1) = 3A + 0B + 1C + 2D
    f(2) = 2A + 3B + 0C + 1D
    f(3) = 1A + 2B + 3C + 0D

    We can see from above that:
    f(0) -> f(1) -> f(2) -> f(3)
    f(i) = f(i - 1) - SUM(A -> D) + N * A[i - 1]

    public class Solution {
        public int maxRotateFunction(int[] A) {
            int n = A.length;
    	int sum = 0;
    	int candidate = 0;
    
    	for (int i = 0; i < n; i++) {
    		sum += A[i];
    		candidate += A[i] * i;
    	}
    	int best = candidate;
    
    	for (int i = 1; i < n; i++) {
    		candidate = candidate - sum + A[i - 1] * n;
    		best = Math.max(best, candidate);
    	}
    	return best;
        }
    }
    

  • 0
    E

    @Davidhunter Thanks, your explanation is much easier to follow than others.
    I think in the formula for computing f(i) you intended to use SUM(A -> D), not SUM(A -> B).


  • 0
    D

    @Eugeneby Thank you


  • 0
    S

    By far the best explanation than others. Thanks!


Log in to reply
 

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