396.Rotate Function

Tags: [DP], [math]

Link: https://leetcode.com/problems/rotate-function/?tab=Description

Given an array of integersAand letnto be its length.

AssumeBkto be an array obtained by rotating the arrayAkpositions clock-wise, we define a "rotation function"FonAas follow:

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

Calculate the maximum value ofF(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 105.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Solution: DP (Dynamic Programming)

class Solution(object):
    def maxRotateFunction(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if not A:
            return 0

        a_len = len(A)
        f = [0 for _ in xrange(a_len)]
        f[0] = sum([i * A[i] for i in xrange(a_len)])
        total = sum(A)

        # DP formula:
        # f[k] = f[k - 1] + total - prev_last_elem - (n - 1) * prev_last_elem
        # prev_last_elem = A[n - 1 - (k - 1)]

        max_v = f[0]
        for k in xrange(1, a_len):
            prev_last_elem = A[a_len - 1 - (k - 1)]
            f[k] = f[k - 1] + total - prev_last_elem - (a_len - 1) * prev_last_elem
            max_v = max(max_v, f[k])

        return max_v

Revelation:

• Try to find what kind of info we can get from the given data, such as, the sum of all elements of the given array.

Note:

• Time complexity = O(n), n is the number of elements of the given array.

Time Limited Exceeded

import sys

class Solution(object):
    def maxRotateFunction(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if not A:
            return 0

        max_v = -sys.maxint - 1
        for k in xrange(len(A)):
            max_v = max(max_v, self.f(A, k))
        return max_v

    def f(self, A, k):
        B = self.generate_B(A, k)

        result = 0
        for i in xrange(len(B)):
            result += i * B[i]

        return result

    def generate_B(self, A, k):
        return list(A[len(A) - k:]) + list(A[:len(A) - k])

Note:

• Time complexity = O(n^2), n is the number of elements of the given array.
• Actually, we don't need use 'list()' to copy the sub array, because we will never modify the original array.