Golang concise O(n) solution


  • 0

    I think an example in a description intentionally makes thing unclear.
    This is easier to understand what is happening on each index.

    A = [4, 3, 2, 6]
    
    F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
    F(1) = (1 * 4) + (2 * 3) + (3 * 2) + (0 * 6) = 4 + 6 + 6 + 0 = 16
    F(2) = (2 * 4) + (3 * 3) + (0 * 2) + (1 * 6) = 8 + 9 + 0 + 6 = 23
    F(3) = (3 * 4) + (0 * 3) + (1 * 2) + (2 * 6) = 12 + 0 + 2 + 12 = 26
    
    So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
    

    When the array shifting from [4,3,2,6] to [6,4,3,2] for instance, the previous result is
    0 * 4 + 3 * 1 + 2 * 2 + 6 * 3 = 25.
    To calculate the sum of [6,4,2,3], first 6 is moved to 0 th index so we need to subtract 6 * 3.

    For other element, each of them move to right by one index, this means we need to add 4 + 3 + 2.
    That is to say, 25 - 18 + 4 + 2 + 3 = 16.

    By appling this method repeatedly, we don't need to iterate twice and can use math to calculate the next rotation, thus O(n).

    func maxRotateFunction(A []int) int {
    	if len(A) == 0 {
    		return 0
    	}
    
    	max := 0
    	digitSum := 0
    	for i, num := range A {
    		max += i * num
    		digitSum += num
    	}
    
    	curMax := max
    	if len(A) > 1 {
    		for i := len(A) - 1; i >= 1; i-- {
    			newMax := curMax - (len(A)-1)*A[i] + (digitSum - A[i])
    			if newMax > max {
    				max = newMax
    			}
    			curMax = newMax
    		}
    	}
    	return max
    }
    

Log in to reply
 

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