Leetcode 396. Rotate Function

문제

You are given an integer array nums of length n.

Assume arr[k] to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:

F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].
Return the maximum value of F(0), F(1), ..., F(n-1).

The test cases are generated so that the answer fits in a 32-bit integer.

• N 길이의 정수 배열이 주어진다.
• k-배열은 배열을 시계방향으로 N번 회전할때 얻어진다고 가정한다.
• 가상의 F(k) 함수에 대해 해당 함수의 값은
  F(k) = 0 arrk[0] + 1 arrk[1] + ... + (n - 1) * arrk[n - 1].
• 위 연산을 수행한 값이라고 가정할때
• 모든 가능한 F(k) 값중 최대값을 리턴하시오

예시

Input: nums = [4,3,2,6]
Output: 26
Explanation:
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
가능한 4가지의 F(k) 값중 최대값은 26이다.

제한

• $n == nums.length$
• $1 <= n <= 10^5$
• $-100 <= nums[i] <= 100$

풀이

• 해당 문제는 자칫 보면 복잡한 prefix sum이 떠오를수 있지만 각 F(0) -> F(1) 등의 전이를 보면 충분히 O(1)로 각 상태를 구할수 있다.
• 예를 들어, [a, b, c, d] 배열에 대해
  • F(0)의 경우는 b + 2c + 3d 이고
  • F(1)의 경우는 a + 2b + 3c 인데
• 0 상태에서 1 상태로 전이될때 값의 변경은 a + b + c - 3d 이다.
• 여기서 잘못 생각하면, prefix sum을 써야 한다고 생각 할수 있으나
• 사실은 위 식은 a + b + c + d - 4d 로도 표현할수 있기에, 전체 합만 미리 구해놓으면 된다.
• 이 전이 공식을 일반화 하면, 배열의 길이가 N일때

$F(i + 1) = F(i) + (sumofarray - 4 * arr[N-i])$

가 된다.

이를 그대로 For loop로 순회시, 전이에는 O(1) 시간복잡도가 소요되고, 전체 전이 횟수가 N-1이기에

시간복잡도가 O(N) 이 된다.

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        N = len(nums)
        ans = sum(i * v for i, v in enumerate(nums))
        val = ans
        summation = sum(nums)

        for target in range(N - 1, 0, -1):
            val += summation - N * nums[target]
            if ans < val:
                ans = val

        return ans